Pagini recente » Cod sursa (job #1769614) | Cod sursa (job #2361032) | Cod sursa (job #481885) | Cod sursa (job #1701424) | Cod sursa (job #2437880)
#include <iostream>
#include <fstream>
#include <queue>
#include <cmath>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int NMAX = 105;
const int oo = 2e9;
int n, m, xr, yr, xj, yj;
char s[NMAX];
int a[NMAX][NMAX], distR[NMAX][NMAX], distJ[NMAX][NMAX];
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
bool Inside(int i,int j)
{
return i <= n && j <= m && i >= 1 && j >= 1;
}
void Lee(int dist[][NMAX], int xstart, int ystart)
{
int i, j, x, y, k;
for(i = 1;i <= n;i++)
for(j = 1;j <= m;j++)
dist[i][j] = oo;
dist[xstart][ystart] = 0;
queue< pair <int, int> >q;
q.push(make_pair(xstart, ystart));
while(!q.empty())
{
i = q.front().first;
j = q.front().second;
q.pop();
for(k = 0;k < 4;k++)
{
x = i + dx[k];
y = j + dy[k];
if(Inside(x, y) && a[x][y] == 0 && dist[x][y] > dist[i][j] + 1)
{
dist[x][y] = dist[i][j] + 1;
q.push(make_pair(x, y));
}
}
}
}
int main()
{
fin >> n >> m;
fin.get();
for (int i = 1;i <= n;++i)
{
fin.getline(s + 1, NMAX);
for (int j = 1;j <= m;++j)
{
if (s[j] == ' ')
a[i][j] = 0;
else if (s[j] == '#')
a[i][j] = 1;
else if (s[j] == 'R')
{
xr = i;
yr = j;
}
else if (s[j] == 'J')
{
xj = i;
yj = j;
}
}
}
Lee(distR, xr, yr);
Lee(distJ, xj, yj);
for(int i = 1;i <= n;i++, cout << "\n")
for(int j = 1;j <= m;j++, cout << " ")
cout << distR[i][j];
cout << "\n";
for(int i = 1;i <= n;i++, cout << "\n")
for(int j = 1;j <= m;j++, cout << " ")
cout << distJ[i][j];
int ans = oo, ansi, ansj;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
if(a[i][j] == 1 || distR[i][j] == oo || distJ[i][j] == oo)
continue;
if(distR[i][j] == distJ[i][j])
{
if (ans > distR[i][j])
{
ans = distR[i][j];
ansi = i;
ansj = j;
}
}
else if(abs(distR[i][j] - distJ[i][j]) == 1)
{
if (ans > max(distR[i][j], distJ[i][j]))
{
ans = max(distR[i][j], distJ[i][j]);
ansi = i;
ansj = j;
}
}
}
fout << ans << " " << ansj << " " << ansi << "\n";
return 0;
}