Pagini recente » Cod sursa (job #2693544) | Cod sursa (job #1435155) | Cod sursa (job #269600) | Cod sursa (job #194469) | Cod sursa (job #212547)
Cod sursa(job #212547)
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
int n,m,i,j,x1,x2,y1,y2;
char a[100][100];
int b[100][100] ,c[100][100];
struct coo {int x,y;};
struct val {int x,y,v;};
queue <coo> coada;
void scan()
{
string s;
char buffer[100];
freopen("rj.in","r",stdin);
scanf("%d %d",&n,&m);
gets(buffer);
for (i=0; i<n; i++)
{
gets(buffer);
s=buffer;
for (j=0; j<=s.length(); j++)
{
if (s[j]=='R')
{
x1=i;
y1=j;
}
if (s[j]=='J')
{
x2=i;
y2=j;
}
a[i][j]=s[j];
}
}
}
void look(int b[100][100], int x1, int y1)
{
int auxx, auxy;
coo nod;
nod.x=x1;
nod.y=y1;
coada.push(nod);
b[x1][y1]=1;
while (coada.size()>0)
{
auxx=coada.front().x;
auxy=coada.front().y;
coada.pop();
if (auxx-1>=0 && a[auxx-1][auxy]!='X' && b[auxx-1][auxy]==0)
{
b[auxx-1][auxy]=b[auxx][auxy]+1;
nod.x=auxx-1;
nod.y=auxy;
coada.push(nod);
}
if (auxy+1<m && a[auxx][auxy+1]!='X' && b[auxx][auxy+1]==0)
{
b[auxx][auxy+1]=b[auxx][auxy]+1;
nod.x=auxx;
nod.y=auxy+1;
coada.push(nod);
}
if (auxx+1<n && a[auxx+1][auxy]!='X' && b[auxx+1][auxy]==0)
{
b[auxx+1][auxy]=b[auxx][auxy]+1;
nod.x=auxx+1;
nod.y=auxy;
coada.push(nod);
}
if (auxy-1>=0 && a[auxx][auxy-1]!='X' && b[auxx][auxy-1]==0)
{
b[auxx][auxy-1]=b[auxx][auxy]+1;
nod.x=auxx;
nod.y=auxy-1;
coada.push(nod);
}
if (auxy+1<m && auxx-1>=0 && a[auxx-1][auxy+1]!='X' && b[auxx-1][auxy+1]==0)
{
b[auxx-1][auxy+1]=b[auxx][auxy]+1;
nod.x=auxx-1;
nod.y=auxy+1;
coada.push(nod);
}
if (auxy+1<m && auxx+1<n && a[auxx+1][auxy+1]!='X' && b[auxx+1][auxy+1]==0)
{
b[auxx+1][auxy+1]=b[auxx][auxy]+1;
nod.x=auxx+1;
nod.y=auxy+1;
coada.push(nod);
}
if (auxy-1>=0 && auxx+1<n && a[auxx+1][auxy-1]!='X' && b[auxx+1][auxy-1]==0)
{
b[auxx+1][auxy-1]=b[auxx][auxy]+1;
nod.x=auxx+1;
nod.y=auxy-1;
coada.push(nod);
}
if (auxy-1>=0 && auxx-1>=0 && a[auxx-1][auxy-1]!='X' && b[auxx-1][auxy-1]==0)
{
b[auxx-1][auxy-1]=b[auxx][auxy]+1;
nod.x=auxx-1;
nod.y=auxy-1;
coada.push(nod);
}
}
}
void search()
{
coo nod;
for (i=0; i<n; i++)
for (j=0; j<m; j++)
if (b[i][j]==c[i][j] && b[i][j]!=0 && c[i][j]!=0)
{
nod.x=i;
nod.y=j;
coada.push(nod);
}
}
int main()
{
val min;
scan();
look(b,x1,y1);
look(c,x2,y2);
cout <<endl;
search();
min.x=coada.front().x;
min.y=coada.front().y;
min.v=b[min.x][min.y];
coada.pop();
while (coada.size()>0)
{
if (min.v>b[coada.front().x][coada.front().y])
{
min.v=b[coada.front().x][coada.front().y];
min.x=coada.front().x;
min.y=coada.front().y;
}
else
if (min.v==b[coada.front().x][coada.front().y] && min.x>coada.front().x)
{
min.x=coada.front().x;
min.y=coada.front().y;
}
else
if (min.v==b[coada.front().x][coada.front().y] && min.x==coada.front().x && min.y>coada.front().y)
{
min.y=coada.front().y;
}
coada.pop();
}
freopen("rj.out","w",stdout);
cout << min.v << " " << min.x+1 << " " << min.y+1;
return 0;
}