Pagini recente » Cod sursa (job #701169) | Cod sursa (job #619349) | Cod sursa (job #216380) | Cod sursa (job #716007) | Cod sursa (job #2668267)
#include <bits/stdc++.h>
#define N 123456789
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
struct punct
{
int x, y;
};
const int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dy[8] = {-1, 1, 0 ,0, -1, 1, -1, 1};
int n, m, x, y, minimum = N, distanta[2][101][101];
bool vizit[2][101][101];
string sir;
punct R, J;
queue <punct> coada;
void BFS(punct P, int tip)
{
coada.push(P);
distanta[tip][P.x][P.y] = 1;
vizit[tip][P.x][P.y] = 1;
while(!coada.empty())
{
punct p = coada.front();
coada.pop();
for(int k = 0; k < 8; k++)
{
int px = p.x + dx[k];
int py = p.y + dy[k];
if(!vizit[tip][px][py])
{
vizit[tip][px][py] = 1;
distanta[tip][px][py] = distanta[tip][p.x][p.y] + 1;
coada.push({px,py});
}
}
}
}
int main()
{
fin>>n>>m;
getline(fin, sir);
for(int i = 1; i <= n; i++)
{
getline(fin, sir);
for(int j = 0; j<min((int)sir.size(), m); j++)
{
vizit[0][i][j + 1] = vizit[1][i][j + 1] = (sir[j] == 'X');
if(sir[j] == 'R')
{
R.x = i;
R.y = j + 1;
}
if(sir[j] == 'J')
{
J.x = i;
J.y = j + 1;
}
}
}
for(int i = 0; i <= n + 1; i++)
vizit[0][i][0] = vizit[1][i][0] = vizit[0][i][m+1] = vizit[1][i][m+1] = 1;
for(int j = 0; j <= m + 1; j++)
vizit[0][0][j] = vizit[1][0][j] = vizit[0][n+1][j] = vizit[1][n+1][j] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <=m; j++)
distanta[0][i][j] = distanta[1][i][j] = N;
BFS(R,0);
BFS(J,1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(distanta[0][i][j] == distanta[1][i][j] && distanta[0][i][j] < minimum)
{
minimum = distanta[0][i][j];
x = i;
y = j;
}
fout << minimum << ' ' << x << ' ' << y;
return 0;
}