Pagini recente » Cod sursa (job #2594175) | Cod sursa (job #2698997) | Cod sursa (job #3217016) | Cod sursa (job #2347637) | Cod sursa (job #189690)
Cod sursa(job #189690)
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define LL long long
#define ULL unsigned long long
#define PB push_back
#define x first
#define y second
using namespace std;
typedef pair<int,int> P;
char m[110][110];
map <P, int> val;
queue <P> stack;
int main(void){
ifstream in("rj.in");
ofstream out("rj.out");
int i,j,N,M;
char C;
P R,J;
in >> N >> M;
in.getline(m[0],0);
for (i=0;i<N;i++)
{
in.getline(m[i],110);
for (j=0;j<M;j++)
{
if (m[i][j]=='R') {R.x = i;R.y = j;}
if (m[i][j]=='J') {J.x = i;J.y = j;}
}
}
stack.push(R);
val[R] = 1;
P Z(-1,-1);
int r;
while (Z != J)
{
Z = stack.front();
stack.pop();
r = val[Z];
//out << Z.x << " " << Z.y << " " << r <<"\n";
if (Z.x > 0 && m[Z.x-1][Z.y]!='X' && val.count(P(Z.x-1,Z.y)) == 0)
{
stack.push(P(Z.x-1,Z.y));
val[P(Z.x-1,Z.y)] = r+1;
}
if (Z.y > 0 && m[Z.x][Z.y-1]!='X' && val.count(P(Z.x,Z.y-1)) == 0)
{
stack.push(P(Z.x,Z.y-1));
val[P(Z.x,Z.y-1)] = r+1;
}
if (Z.x <N-1 && m[Z.x+1][Z.y]!='X' && val.count(P(Z.x+1,Z.y)) == 0)
{
stack.push(P(Z.x+1,Z.y));
val[P(Z.x+1,Z.y)] = r+1;
}
if (Z.y <M-1 && m[Z.x][Z.y+1]!='X' && val.count(P(Z.x,Z.y+1)) == 0)
{
stack.push(P(Z.x,Z.y+1));
val[P(Z.x,Z.y+1)] = r+1;
}
}
P sol(999,999);
int max= val[J];
r = max;
out << max/2 << " ";
Z = J;
while (r!=1)
{
if (Z.x > 0 && val.count(P(Z.x-1,Z.y)) != 0 && val[P(Z.x-1,Z.y)] == r-1)
{
Z.x--;r--;
int dist = max+1 - 2*r;
if (abs( dist ) <2)
sol = Z;
}
if (Z.y > 0 && val.count(P(Z.x,Z.y-1)) != 0 && val[P(Z.x,Z.y-1)] == r-1)
{
Z.y--;r--;
int dist = max+1 - 2*r;
if (abs( dist ) <2)
sol = Z;
}
if (Z.x <N-1 && val.count(P(Z.x+1,Z.y)) != 0 && val[P(Z.x+1,Z.y)] == r-1)
{
Z.x++;r--;
int dist = max+1 - 2*r;
if (abs( dist ) <2)
sol = Z;
}
if (Z.y <M-1 && val.count(P(Z.x,Z.y+1)) != 0 && val[P(Z.x,Z.y+1)] == r-1)
{
Z.y++;r--;
int dist = max+1 - 2*r;
if (abs( dist ) <2)
sol = Z;
}
}
out << sol.x+1 << " " << sol.y+1;
in.close();
out.close();
return 0;
}