Pagini recente » Cod sursa (job #1048955) | Cod sursa (job #1496613) | Cod sursa (job #1216143) | Cod sursa (job #520813) | Cod sursa (job #3138465)
#include <bits/stdc++.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n,m;
int a[101][101];
int rom[101][101];
int jul[101][101];
int di[]={-1,0,1,0,1,1,-1,-1};
int dj[]={0,1,0,-1,1,-1,1,-1};
int x[10001];
int y[10001];
int traseu[101][101];
bool inmat(int i,int j)
{
return i<=n && i>=1 && j>=1 && j<=m;
}
int lee(int a[101][101],int x1,int y1,int x2,int y2)
{
int p=1,u=1;
int i,j;
int ii,ij;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
traseu[i][j]=0;
traseu[x1][y1]=1;
x[1]=x1;
y[1]=y1;
while(p<=u)
{
i=x[p];
j=y[p];
int k;
for(k=0;k<8;k++)
{
ii=i+di[k];
ij=j+dj[k];
if(inmat(ii,ij) && a[ii][ij]!=1 && traseu[ii][ij]==0)
{
u++;
x[u]=ii;
y[u]=ij;
traseu[ii][ij]=traseu[i][j]+1;
}
}
if(traseu[x2][y2]!=0)
return traseu[x2][y2];
p++;
}
return n*m+1;
}
int main()
{
f>>n>>m;
int i,j;
char ch;
int x1,y1,x2,y2;
for(i=1;i<=n;i++)
{
f.get();
for(j=1;j<=m;j++)
{
f.get(ch);
if(ch==' ')
a[i][j]=0;
else
if(ch=='X')
a[i][j]=1;
else
if(ch=='R')
{
a[i][j]=2;
x1=i;
y1=j;
}
else
{
a[i][j]=3;
x2=i;
y2=j;
}
}
}
int lin,col;
lin=0,col=0;
int minim=1e10;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]==0)
{
int drum1=lee(a,x1,y1,i,j);
int drum2=lee(a,x2,y2,i,j);
rom[i][j]=drum1;
jul[i][j]=drum2;
}
else
{
rom[i][j]=-1;
jul[i][j]=-1;
}
if(rom[i][j]!=n*m+1 && jul[i][j]!=n*m+1 && rom[i][j]>0 && jul[i][j]>0)
{
if(rom[i][j]==jul[i][j])
{
if(minim>rom[i][j])
{
minim=rom[i][j];
lin=i;
col=j;
}
}
}
}
}
g<<minim<<" "<<lin<<" "<<col;
return 0;
}