Pagini recente » Cod sursa (job #1469263) | Cod sursa (job #753042) | Cod sursa (job #2933486) | Cod sursa (job #3229628) | Cod sursa (job #735174)
Cod sursa(job #735174)
#include<fstream>
using namespace std;
int A[110][110],B[110][110];
int n,m;
int xr,yr,xj,yj;
int V[8] = {0,0,1,1,1,-1,-1,-1};
int C[8] = {1,-1,0,1,-1,0,1,-1};
struct coord{
int x,y;
}q[10001];
ifstream f("rj.in");
ofstream g("rj.out");
int main()
{
f>>n>>m;
int cx = 0,cy = 0,tmax = 1000000;
f.get();
char s[110];
int i,j;
for(i = 1;i<=n;++i)
{
f.getline(s,110);
for(j = 0;j<m;++j)
{
if(s[j] ==' ')
{
A[i][j+1] = 0;
B[i][j+1] = 0;
}
else if(s[j] == 'X')
{
A[i][j+1] = -1;
B[i][j+1] = -1;
}
else if(s[j] == 'R')
{
xr = i; yr = j+1;
}
else {
xj = i; yj = j+1;
}
}
}
f.close();
for(int i = 0;i<=n+1;++i)
A[i][0] = B[i][0] = A[i][n+1] = B[i][n+1] = -1;
for(int i = 0;i<=m+1;++i)
A[0][i] = B[0][i] = A[n+1][i] = B[n+1][i] = -1;
int x,y,k,ul = 0,pr = 0;
A[xr][yr] = 1;
q[ul].x = xr;
q[ul].y = yr;
while(pr <= ul)
{
x = q[pr].x;
y = q[pr].y;
++pr;
for(k = 0;k<8;++k)
{
i = x+V[k];
j = y+C[k];
if(A[i][j] == 0)
{
++ul;
q[ul].x = i;
q[ul].y =j;
A[i][j] = A[x][y] + 1;
}
}
}
int ul1 = 0;
int pr1 = 0;
B[xj][yj] = 1;
q[ul1].x = xj;
q[ul1].y = yj;
while(pr1 <= ul1)
{
x = q[pr1].x;
y = q[pr1].y;
++pr1;
for(k = 0;k<8;++k)
{
i = x+V[k];
j = y+C[k];
if(B[i][j] == 0)
{
++ul1;
q[ul1].x = i;
q[ul1].y =j;
B[i][j] = B[x][y] + 1;
}
}
}
for(i = 1;i<=n;++i)
{
for(j = 1;j<=m;++j)
if(A[i][j] == B[i][j] && A[i][j]>0)
if(A[i][j]<tmax)
{
tmax = A[i][j];
cx = i;
cy = j;
}
}
g<<tmax << " " << cx << " " <<cy;
g.close();
return 0;
}