Pagini recente » Monitorul de evaluare | Cod sursa (job #706079) | Cod sursa (job #930431) | Cod sursa (job #1274554) | Cod sursa (job #1636730)
#include<fstream>
#include<climits>
#include<cstring>
#include<queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int N,M,Solx,Soly,Tmin = INT_MAX;
int A1[128][128],A2[128][128];
char L[128];
int dx[]={-1,0,1,1,1,0,-1,-1};
int dy[]={1,1,1,0,-1,-1,-1,0};
queue < pair<int,int> > Q1,Q2;
void Read()
{
fin>>N>>M; fin.get();
for(int i=1;i<=N;++i)
{
fin.getline(L,128);
for(int j=0;j<M;++j)
{
if(L[j] == 'X') A1[i][j+1] = A2[i][j+1] = -1;
else
if(L[j] == 'R')
{
Q1.push(make_pair(i,j+1));
A1[i][j+1] = 1;
}
else
if(L[j] == 'J')
{
Q2.push(make_pair(i,j+1));
A2[i][j+1] = 1;
}
}
}
}
void Lee()
{
for(int i=0;i<= N+1;++i)
A1[i][0] = A1[i][M+1] = A2[i][0] = A2[i][M+1] = -1;
for(int i = 0; i <= M+1; i++)
A1[0][i] = A1[N+1][i] = A2[0][i] = A2[N+1][i] = -1;
while(!Q1.empty())
{
int X=Q1.front().first;
int Y=Q1.front().second;
Q1.pop();
for(int j=0;j<8;j++)
{
int XNew = X + dx[j];
int YNew = Y + dy[j];
if(A1[XNew][YNew] == 0)
{
A1[XNew][YNew] = A1[X][Y] + 1;
Q1.push(make_pair(XNew,YNew));
}
}
}
while(!Q2.empty())
{
int X=Q2.front().first;
int Y=Q2.front().second;
Q2.pop();
for(int j=0;j<8;j++)
{
int XNew = X + dx[j];
int YNew = Y + dy[j];
if(A2[XNew][YNew] == 0)
{
A2[XNew][YNew] = A2[X][Y] + 1;
Q2.push(make_pair(XNew,YNew));
}
}
}
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
if(A1[i][j] == A2[i][j] && A1[i][j] > 0 && A1[i][j] < Tmin)
{ Tmin = A1[i][j]; Solx = i; Soly = j; }}
int main()
{
Read();
Lee();
fout<<Tmin<<" "<<Solx<<" "<<Soly<<"\n";
fin.close();
fout.close();
return 0;
}