Pagini recente » Cod sursa (job #2751816) | Cod sursa (job #110504) | Cod sursa (job #29236) | Cod sursa (job #817126) | Cod sursa (job #881027)
Cod sursa(job #881027)
#include <cstdio>
#include <queue>
#define N 102
using namespace std;
bool map[N][N];
int dR[N][N],dJ[N][N];
int n,m;
const int dlin[] = {1,-1,0,0,1,-1,1,-1};
const int dcol[] = {0,0,1,-1,1,1,-1,-1};
struct elem
{
int lin,col;
} res;
queue <elem> qR,qJ;
bool accesibil(elem p)
{
if(map[p.lin][p.col]) return 0;
if(p.lin>=n) return 0;
if(p.lin<0) return 0;
if(p.col>=m) return 0;
if(p.col<0) return 0;
return 1;
}
void read()
{
char c[102];
elem p;
scanf("%d %d\n",&n,&m);
for(int i=0;i<n;++i)
{
gets(c);
for(int j=0;j<m;++j)
{
if(c[j] == 'X') map[i][j]=1;
//else if(c[j] == ' ') ;
else if(c[j]== 'R')
{
p.col=j, p.lin=i;
qR.push(p);
dR[i][j]=1;
//map[i][j]=1;
}
else if(c[j]== 'J')
{
p.col=j, p.lin=i;
qJ.push(p);
dJ[i][j]=1;
//map[i][j]=2;
}
}
}
}
elem run()
{
elem a,b;
while(! qR.empty())
{
a=qR.front();
qR.pop();
for(int i=0;i<8;++i)
{
b.col = a.col+dcol[i];
b.lin = a.lin+dlin[i];
if(accesibil(b) && dR[b.lin][b.col]==0)
{
qR.push(b);
dR[b.lin][b.col] = dR[a.lin][a.col]+1;
}
}
}
while(! qJ.empty())
{
a=qJ.front();
qJ.pop();
for(int i=0;i<8;++i)
{
b.col = a.col+dcol[i];
b.lin = a.lin+dlin[i];
if(accesibil(b) && dJ[b.lin][b.col]==0)
{
qJ.push(b);
dJ[b.lin][b.col] = dJ[a.lin][a.col]+1;
}
}
}
int min = 99999;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(dR[i][j]>0)
if(dR[i][j]==dJ[i][j])
if(dR[i][j]<min)
{
min=dR[i][j];
a.lin = i;
a.col = j;
//printf("f ");
}
return a;
}
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
read();
res = run();
/*for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
printf("%d ",dR[i][j]);
printf("\n");
}
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
printf("%d ",dJ[i][j]);
printf("\n");
}*/
printf("%d %d %d",dR[res.lin][res.col],1+res.lin,1+res.col);
return 0;
}