Pagini recente » Cod sursa (job #2892533) | Cod sursa (job #2327591) | Cod sursa (job #1665325) | Cod sursa (job #1393207) | Cod sursa (job #2187447)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int MAXN = 105;
int mat[MAXN][MAXN];
int leeR[MAXN][MAXN];
int leeJ[MAXN][MAXN];
queue < pair < int, int > > Q;
int di[] = {-1,-1,-1,0,1,1,1,0};
int dj[] = {-1,0,1,1,1,0,-1,-1};
int n, m;
bool valid(int i, int j)
{
if (i < 1 || i > n || j < 1 || j > m) return 0;
if (mat[i][j] == 1 || leeR[i][j]) return 0;
return 1;
}
bool ok(int i, int j)
{
if (i < 1 || i > n || j < 1 || j > m) return 0;
if (mat[i][j] == 1 || leeJ[i][j]) return 0;
return 1;
}
int main()
{
int i, j, iR, jR, iJ, jJ, i_nou, j_nou, x, y, tmin = 50005;
string sir;
fin >> n >> m;
for (i = 0; i <= n; ++i)
{
getline(fin,sir);
for (j = 0; j < sir.length(); ++j)
{
if (sir[j] == 'R')
{
mat[i][j + 1] = 2;
iR = i;
jR = j + 1;
}
else if (sir[j] == 'J')
{
mat[i][j + 1] = 2;
iJ = i;
jJ = j + 1;
}
else if (sir[j] == 'X')
{
mat[i][j + 1] = 1;
}
else mat[i][j + 1] = 0;
}
}
Q.push({iR, jR});
leeR[iR][jR] = leeJ[iJ][jJ] = 1;
while (!Q.empty())
{
i = Q.front().first;
j = Q.front().second;
Q.pop();
for (int k = 0; k < 8; ++k)
{
i_nou = i + di[k];
j_nou = j + dj[k];
if (valid(i_nou,j_nou))
{
leeR[i_nou][j_nou] = leeR[i][j] + 1;
Q.push({i_nou,j_nou});
}
}
}
Q.push({iJ, jJ});
while (!Q.empty())
{
i = Q.front().first;
j = Q.front().second;
Q.pop();
for (int k = 0; k < 8; ++k)
{
i_nou = i + di[k];
j_nou = j + dj[k];
if (ok(i_nou, j_nou))
{
leeJ[i_nou][j_nou] = leeJ[i][j] + 1;
Q.push({i_nou, j_nou});
}
}
}
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= m; ++j)
{
if (leeR[i][j] == leeJ[i][j] && leeR[i][j])
{
if (leeR[i][j] < tmin)
{
tmin = leeR[i][j];
x = i;
y = j;
}
}
}
}
fout << tmin << " " << x << " " << y << "\n";
return 0;
}