Pagini recente » Cod sursa (job #2788072) | Cod sursa (job #2433485) | Cod sursa (job #2765606) | Cod sursa (job #340250) | Cod sursa (job #1349547)
#include <cstdio>
#include <queue>
using namespace std;
const int MAX_N = 100, MAX_M = 100;
const int dlin[] = {-1,-1,-1,0,0,1,1,1};
const int dcol[] = {-1,0,1,-1,1,-1,0,1};
FILE *in, *out;
int a[MAX_N+2][MAX_M+2], romeo[MAX_N+2][MAX_M+2], julieta[MAX_N+2][MAX_M+2];
bool viz[MAX_N+2][MAX_M+2];
int n, m;
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++)
a[i][0] = a[i][m+1] = -1;
for(int j = 0; j <= m+1; j++)
a[0][j] = a[n+1][j] = -1;
}
void rlee()
{
poz x, y;
int i;
while(!q.empty())
{
x = q.front();
q.pop();
viz[x.lin][x.col] = true;
for(i = 0; i < 8; i++)
{
y.lin = x.lin + dlin[i];
y.col = x.col + dcol[i];
if(a[y.lin][y.col] != -1 && !viz[y.lin][y.col])
{
q.push(y);
romeo[y.lin][y.col] = romeo[x.lin][x.col]+1;
viz[y.lin][y.col] = true;
}
}
}
}
void jlee()
{
poz x, y;
int i;
while(!q.empty())
{
x = q.front();
q.pop();
viz[x.lin][x.col] = false;
for(i = 0; i < 8; i++)
{
y.lin = x.lin + dlin[i];
y.col = x.col + dcol[i];
if(a[y.lin][y.col] != -1 && viz[y.lin][y.col])
{
q.push(y);
julieta[y.lin][y.col] = julieta[x.lin][x.col]+1;
viz[y.lin][y.col] = false;
}
}
}
}
int main()
{
in = fopen("rj.in", "r");
out = fopen("rj.out", "w");
fscanf(in, "%d%d", &n, &m);
int i, j;
char c;
poz rom, jul;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
fscanf(in, "%c", &c);
if(c == 'R')
{
rom.lin = i;
rom.col = j;
a[i][j] = 1;
} else if(c == 'J') {
jul.lin = i;
jul.col = j;
a[i][j] = 2;
} else if(c == 'X') a[i][j] = -1;
}
if(fscanf(in,"\n"));
}
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 <= n; 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);
}
}
}
fprintf(out, "%d %d %d", tmin, lin, col);
fclose(in);
fclose(out);
return 0;
}