Cod sursa(job #819496)

Utilizator nicnic28nichita trita nicnic28 Data 19 noiembrie 2012 10:19:53
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#include<queue>

using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");

const int dlin[]={0,1,0,-1};
const int dcol[]={1,0,-1,0};
const int N=102;
int ro[N][N],ju[N][N];
int n,m,cmin=42,mini,minj;
char t[N];

struct poz{
    int lin,col;
    /*poz(int i,int j){
        lin=i;
        col=j;
    }*/
}rom,jul;
queue<poz> q;
void bfs(int a[N][N],poz start){
    poz x,y;
    for(int i=0 ; i<=m ; i++){
        a[i][0]=-2;
        a[i][m+1]=-2;
    }
    for(int i=1 ; i<=n ; i++){
        a[0][i]=-2;
        a[n+1][i]=-2;
    }
    a[start.lin][start.col]=0;
    q.push(start);
    while(!q.empty()){
        x=q.front();
        q.pop();
        for(int i=0 ; i<4 ; i++){
            y.lin=x.lin+dlin[i];
            y.col=x.col+dcol[i];
                if(a[y.lin][y.col]==-1){
                    a[y.lin][y.col]=1+a[x.lin][x.col];
                    q.push(y);
                }
        }
    }
}

int main()
{
    in>>n>>m>>ws;
    for(int i=1 ; i<=n ; i++){
        in.getline(t,251);
        for(int j=1 ; j<=m ; j++){
            switch(t[j-1]){
            case ' ': ro[i][j]=ju[i][j]=-1;break;
            case 'R': rom.lin=i;rom.col=j;break;
            case 'J': jul.lin=i;jul.col=j;break;
            case 'X': ro[i][j]=ju[i][j]=-2;break;
            }
        }
    }
    bfs(ro,rom);
    bfs(ju,jul);
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            if((ro[i][j]>0) && (ju[i][j]>0) && (ro[i][j]==ju[i][j]) && (ro[i][j]<cmin)){
                cmin=ro[i][j];
                mini=i;
                minj=j;
            }
        }
    }
    out<<cmin<<' '<<mini<<' '<<minj;
    return 0;
}