Pagini recente » Cod sursa (job #1788309) | Cod sursa (job #69988) | Cod sursa (job #1349760) | Cod sursa (job #2525787) | Cod sursa (job #1349600)
#include <cstdio>
#include <queue>
using namespace std;
const int MAX_N = 100, MAX_M = 100;
const int dlin[]= {-1,-1,0,1,1,1,0,-1};
const int dcol[]= {0,-1,-1,-1,0,1,1,1};
int romeo[MAX_N+2][MAX_M+2], julieta[MAX_N+2][MAX_M+2];
int n, m;
char a[MAX_N+2][MAX_M+2];
inline int minim(int a, int b)
{
return (a<b)?a:b;
}
struct poz {
int lin, col;
};
queue<poz> q;
void bordare()
{
for(int i = 0; i <= n+1; i++)
romeo[i][0] = romeo[i][m+1] = julieta[i][0] = julieta[i][m+1] = n*m+1;
for(int j = 0; j <= m+1; j++)
romeo[0][j] = romeo[n+1][j] = julieta[0][j] = julieta[n+1][j] = n*m+1;
}
void rlee()
{
poz x, y;
int i;
while(!q.empty())
{
x = q.front();
q.pop();
for(i = 0; i < 8; i++)
{
y.lin = x.lin + dlin[i];
y.col = x.col + dcol[i];
if(romeo[y.lin][y.col] == 0)
{
q.push(y);
romeo[y.lin][y.col] = romeo[x.lin][x.col]+1;
}
}
}
}
void jlee()
{
poz x, y;
int i;
while(!q.empty())
{
x = q.front();
q.pop();
for(i = 0; i < 8; i++)
{
y.lin = x.lin + dlin[i];
y.col = x.col + dcol[i];
if(julieta[y.lin][y.col] == 0)
{
q.push(y);
julieta[y.lin][y.col] = julieta[x.lin][x.col]+1;
}
}
}
}
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
scanf("%d%d\n", &n, &m);
int i, j;
poz rom, jul;
for(i = 1; i <= n; i++)
{
gets(1+a[i]);
for(j = 1; j <= m; j++)
{
if(a[i][j] == 'R')
{
rom.lin = i;
rom.col = j;
} else if(a[i][j] == 'J') {
jul.lin = i;
jul.col = j;
} else if(a[i][j] == 'X')
romeo[i][j] = julieta[i][j] = n*m+1;
}
}
bordare();
romeo[rom.lin][rom.col] = 1;
julieta[jul.lin][jul.col] = 1;
q.push(rom);
rlee();
q.push(jul);
jlee();
int tmin = n*m+1;
int lin = n+1, col = m+1;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
{
if((romeo[i][j] == julieta[i][j]) && (romeo[i][j] != 0))
{
if(tmin > romeo[i][j])
{
tmin = romeo[i][j];
lin = i;
col = j;
} else if(tmin == romeo[i][j])
{
if(i < lin)
{
lin = i;
col = j;
} else if(i == lin)
col = minim(col,j);
}
}
}
printf("%d %d %d", tmin, lin, col);
return 0;
}