Pagini recente » Cod sursa (job #53085) | Cod sursa (job #3143925) | Cod sursa (job #239376) | Cod sursa (job #99658) | Cod sursa (job #865711)
Cod sursa(job #865711)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define pp pair<int,int>
#define ox first
#define oy second
#define Nmax 102
using namespace std;
int dl[]={-1,-1,0,1,1,1,0,-1};
int dc[]={0,1,1,1,0,-1,-1,-1};
int mat[Nmax][Nmax];
int romeo[Nmax][Nmax];
int julieta[Nmax][Nmax];
int n,m,sol,poz1,poz2,k;
char c;
int xR,yR,xJ,yJ;
queue <pp> QR,QJ;
void citire(){
FILE *f=fopen("rj.in","r");
fscanf(f,"%d%d%c",&n,&m,&c);
for(int i=1; i<=n; i++)
for(int j=1; j<=m+1; j++){
fscanf(f,"%c",&c);
if(c!='\n'){
if(c==' ')
mat[i][j]=0;
else
if(c=='R'){
xR=i;
yR=j;
}
else
if(c=='J'){
xJ=i;
yJ=j;
}
else
if(c=='X')
mat[i][j]=-1;
}
}
}
void bordare(){
for(int i=0;i<=m+1;i++)
mat[0][i]=mat[n+1][i]=-1;
for(int i=0;i<=n+1;i++)
mat[i][0]=mat[i][m+1]=-1;
}
void lee(){
pp current,v;
sol=-1;
QR.push(make_pair(xR,yR));
QJ.push(make_pair(xJ,yJ));
romeo[xR][yR]=1;
julieta[xJ][yJ]=1;
while(!QR.empty() || !QJ.empty()){
current=QR.front();
for(k=0;k<8;k++){
v.ox=current.ox+dl[k];
v.oy=current.oy+dc[k];
if(romeo[v.ox][v.oy]==0 && mat[v.ox][v.oy]==0){
romeo[v.ox][v.oy]=romeo[current.ox][current.oy]+1;
QR.push(make_pair(v.ox,v.oy));
}
}
QR.pop();
current=QJ.front();
for(k=0;k<8;k++){
v.ox=current.ox+dl[k];
v.oy=current.oy+dc[k];
if(julieta[v.ox][v.oy]==0 && mat[v.ox][v.oy]==0){
julieta[v.ox][v.oy]=julieta[current.ox][current.oy]+1;
QJ.push(make_pair(v.ox,v.oy));
}
}
QJ.pop();
}
}
void gaseste(){
sol=100000;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(romeo[i][j]==julieta[i][j] &&
romeo[i][j] && julieta[i][j] &&
sol>romeo[i][j]){
sol=romeo[i][j];
poz1=i;
poz2=j;
}
}
void afis(){
FILE *g=fopen("rj.out","w");
fprintf(g,"%d %d %d",sol,poz1,poz2);
}
int main()
{
citire();
bordare();
lee();
gaseste();
afis();
return 0;
}