Cod sursa(job #758060)

Utilizator Victor10Oltean Victor Victor10 Data 14 iunie 2012 12:33:28
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> per;

per ro,ju;

struct solutii{
	int t,x,y;
};
solutii sol[105];
int sz;
 
#define bm 105
 
char matc[bm][bm];
int mat1[bm][bm],mat2[bm][bm];
int n,m;
queue <per> a;
 
 
int dx[]={0, 1, 1, 1, 0, -1, -1, -1};
int dy[]={-1, -1, 0, 1, 1, 1, 0, -1};
 
int check(int i,int j){
        if(i<1||j<1||i>n||j>m) return 0;
        return 1;
}
 
void start(int mat[bm][bm],per c){
                int i;
				a.push(make_pair(c.first,c.second));
        for(;a.size();a.pop()){
                per fr=a.front();
                for(i=0;i<8;++i){
                        int ii=fr.first+dy[i],jj=fr.second+dx[i];
                        if(check(ii,jj)&&mat[ii][jj]==0){
                                mat[ii][jj]=mat[fr.first][fr.second]+1;
                                a.push(make_pair(ii,jj));
                        }
                }
        }
                                
}
 
int main(){
        int i,j;
		int tmin=9999,xfin,yfin;
        freopen("rj.in","r",stdin);
       // freopen("rj.out","w",stdout);
        
        scanf("%d %d\n",&n,&m);
        
        for(i=1;i<=n;++i){
                fgets(matc[i]+1,5555,stdin);
        }
        for(i=1;i<=n;++i)
                for(j=1;j<=m;++j){
                        if(matc[i][j]=='R'){
                                mat1[i][j]=1;
                                ro.first=i;ro.second=j;
                                mat2[i][j]=-1;
                        }
                        if(matc[i][j]=='J'){
                                mat1[i][j]=-1;
                               ju.first=i;ju.second=j;
                                mat2[i][j]=1;
                        }
                        if(matc[i][j]=='X'){
                                mat1[i][j]=-1;
                                mat2[i][j]=-1;
                        }
                }
		start(mat2,ju);
		start(mat1,ro);
        for(i=1;i<=n;++i)
                for(j=1;j<=m;++j)
					if(mat1[i][j]==mat2[i][j]&&mat1[i][j]!=-1&&mat1[i][j]!=0){
						++sz;
						sol[sz].t=mat1[i][j];
						sol[sz].x=i;
						sol[sz].y=j;
					}
		for(i=1;i<=sz;++i){
			if(sol[i].t<tmin){
				tmin=sol[i].t;
				xfin=sol[i].x;
				yfin=sol[i].y;
			}

					
		}
		for(i=1;i<=n;i++){
			for(j=1;j<=m;++j)
				printf("%d ", mat2[i][j]);
			printf("\n");
		}
                        
        printf("%d %d %d", tmin, xfin, yfin);        
        
}