Pagini recente » Cod sursa (job #1868886) | Cod sursa (job #974950) | Cod sursa (job #234456) | Cod sursa (job #1449810) | Cod sursa (job #2345226)
#include <queue>
#include <string>
#include <fstream>
#define x first
#define y second
#define len 101
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
typedef pair<int, int> p;
queue<p> q;
int const diri[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dirj[] = {-1, 0, 1, -1, 1, -1, 0, 1}, inf = 0x3f3f3f3f;
p start, finish;
int N, M, rmat[len][len], jmat[len][len];
bool inside(int l, int c)
{
return l >= 1 && l <= N && c >= 1 && c <= M;
}
int main()
{
in >> N >> M;
in.get();
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
rmat[i][j] = jmat[i][j] = inf;
for(int i = 1; i <= N; ++i)
{
string s;
getline(in, s);
for(int j = 1; j <= M; ++j)
{
if(s[j - 1] == 'X')
rmat[i][j] = jmat[i][j] = -1;
else if(s[j - 1] == 'R')
{
start.x = i;
start.y = j;
rmat[i][j] = 1;
q.push({i, j});
}
else if(s[j - 1] == 'J')
{
finish.x = i;
finish.y = j;
}
}
}
while(!q.empty())
{
int i = q.front().x, j = q.front().y;
q.pop();
for(int k = 0; k < 8; ++k)
{
int ii = i + diri[k], jj = j + dirj[k];
if(inside(ii, jj) && rmat[ii][jj] != -1 && rmat[ii][jj] > rmat[i][j] + 1)
{
rmat[ii][jj] = rmat[i][j] + 1;
q.push({ii, jj});
}
}
}
jmat[finish.x][finish.y] = 1;
q.push({finish.x, finish.y});
while(!q.empty())
{
int i = q.front().x, j = q.front().y;
q.pop();
for(int k = 0; k < 8; ++k)
{
int ii = i + diri[k], jj = j + dirj[k];
if(inside(ii, jj) && jmat[ii][jj] != -1 && jmat[ii][jj] > jmat[i][j] + 1)
{
jmat[ii][jj] = jmat[i][j] + 1;
q.push({ii, jj});
}
}
}
int dist = rmat[finish.x][finish.y], mij = dist / 2 + dist % 2;
out << mij << ' ';
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
if(dist % 2 && rmat[i][j] == mij && jmat[i][j] == mij)
{
out << i << ' ' << j;
return 0;
}
else if(!(dist % 2) && rmat[i][j] == mij && jmat[i][j] == mij + 1)
{
out << i << ' ' << j;
return 0;
}
}