Cod sursa(job #271825)

Utilizator razyelxrazyelx razyelx Data 5 martie 2009 23:16:07
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream.h>
#include <string.h>
#define max 110
ifstream in("rj.in");
ofstream out("rj.out");

int n,m,tr[max][max],tj[max][max];
char t[max];

struct poz{int x,y;} r,ju;

int x[10]={0,1,1,1,0,0,-1,-1,-1};
int y[10]={0,-1,0,1,-1,1,-1,0,1};

void citire(){
     int i,j;

     in>>n>>m;
     in.get();
     for(i=1;i<=n;++i){
	in.getline(t,109);
	for(j=1;j<=m;++j){

	   if(t[j-1] == 'X') tr[i][j] = tj[i][j] = -1;
	   if(t[j-1] == 'R'){r.x = i;r.y=j;}
	   if(t[j-1] == 'J'){ju.x = i;ju.y=j;}
	}
     }
}
void bordare(){
     int i,j;
     for(j=0;j<=m+1;++j)
	tr[n+1][j] = tr[0][j] = tj[n+1][j] = tj[0][j] = -1;
     for(i=0;i<=n+1;++i)
	tr[i][m+1] = tr[i][0] = tj[i][m+1] = tj[i][0] = -1;
}
void bfs(int m[max][max],poz s){
     int prim,ultim,k;
     poz pivot,coada[max];

     prim = ultim = 1;
     m[s.x][s.y]  = 1;
     coada[prim].x = s.x;
     coada[prim].y = s.y;

     while(prim<=ultim){

	  for(k=1;k<=8;++k)
	     if(m[coada[prim].x + x[k]][coada[prim].y + y[k]] == 0)
	       if(m[coada[prim].x + x[k]][coada[prim].y + y[k]] < m[coada[prim].x][coada[prim].y]+1){
		 m[coada[prim].x + x[k]][coada[prim].y + y[k]] = m[coada[prim].x][coada[prim].y]+1;
		 ultim++;
		 coada[ultim].x = coada[prim].x + x[k];
		 coada[ultim].y = coada[prim].y + y[k];
	       }
	  prim++;
     }

}
void afisare(){
     int i,j,x=101,y=101,tmin=32000;

     for(i=1;i<=n;++i)
	for(j=1;j<=m;++j)

	   if(tr[i][j] == tj[i][j] && tr[i][j]!=-1 && tr[i][j] !=0)
	     if(tmin > tr[i][j]){
	       tmin = tr[i][j];
	       x = i;
	       y = j;
	     }
     out<<tmin<<" "<<x<<" "<<y;
}
int main(){
    citire();
    bordare();
    bfs(tr,r);
    bfs(tj,ju);
    afisare();
    return 0;
}