Pagini recente » Cod sursa (job #3284154) | Cod sursa (job #3297179)
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, iJ, jJ, iR, jR;
char mat[N][N];
int distJ[N][N], distR[N][N];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
bool inside(int i, int j)
{
return i >= 1 && i <= n && j >= 1 && j <= n;
}
void bfs(int si, int sj, int dist[N][N])
{
queue<pair<int, int>> q;
q.push(make_pair(si, sj));
dist[si][sj] = 0;
while (!q.empty())
{
int i = q.front().first;
int j = q.front().second;
q.pop();
for (int d = 0; d < 8; d++)
{
int ni = i + dx[d];
int nj = j + dy[d];
if (inside(ni, nj) && mat[ni][nj] != 'X' && dist[ni][nj] == -1)
{
dist[ni][nj] = dist[i][j] + 1;
q.push(make_pair(ni, nj));
}
}
}
}
int main()
{
freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
cin >> n;
getchar();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
char c;
cin.get(c);
if (c == ' ')
{
mat[i][j] = 0;
}
else if (c == 'X')
{
mat[i][j] = -1;
}
else if (c == 'J')
{
iJ = i;
jJ = j;
mat[i][j] = 0;
}
else if (c == 'R')
{
iR = i;
jR = j;
mat[i][j] = c;
}
}
getchar();
}
memset(distJ, -1, sizeof(distJ));
memset(distR, -1, sizeof(distR));
bfs(iJ, jJ, distJ);
bfs(iR, jR, distR);
int minStep = INT_MAX;
int ifinal = -1, jfinal = -1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (distJ[i][j] != -1 && distJ[i][j] == distR[i][j])
{
if (distJ[i][j] < minStep ||
(distJ[i][j] == minStep && j < jfinal))
{
minStep = distJ[i][j];
ifinal = i;
jfinal = j;
}
}
}
}
cout << minStep << " " << ifinal << " " << jfinal - 1 << "\n";
return 0;
}