Cod sursa(job #1641195)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 8 martie 2016 21:34:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <queue>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int n,m,M[102][102],rx,ry,jx,jy;
int T[102][102][2];
int dx[8]={0,0,1,-1,1,1,-1,-1},dy[8]={1,-1,0,0,1,-1,1,-1};
struct elem{
    int x,y,t;
}a,b;
queue<elem> Q;
void brod(){
    for(int i=0;i<=n+1;i++){
        M[i][0]=-1;
        M[i][m+1]=-1;
    }
    for(int i=0;i<=m+1;i++){
        M[0][i]=-1;
        M[n+1][i]=-1;
    }
}
void read(){
    in>>n>>m;
    char LINE[101];
    in.getline(LINE,1);
    for(int i=1;i<=n;i++){
        in.getline(LINE,101);
        for(int j=0;j<m;j++){
            if(LINE[j]=='X')
                M[i][j+1]=-1;
            else if(LINE[j]=='R')
                rx=i,ry=j+1,M[i][j+1]=-1;
            else if(LINE[j]=='J')
                jx=i,jy=j+1,M[i][j+1]=-1;
        }
    }
}
void lee(int xx,int yy,int var){
    a.x=xx;
    a.y=yy;
    a.t=1;
    Q.push(a);
    while(!Q.empty()){
        a=Q.front();
        for(int i=0;i<=7;i++){
            b=a;
            b.x+=dx[i];
            b.y+=dy[i];
            b.t++;
            if(M[b.x][b.y]==0&&T[b.x][b.y][var]==0){
                T[b.x][b.y][var]=b.t;
                Q.push(b);
            }
        }
        Q.pop();
    }
}
void solve(){
    int tmin=100000,tx,ty;
    brod();
    lee(rx,ry,0);
    lee(jx,jy,1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(T[i][j][0]==T[i][j][1]&&T[i][j][0]!=0&&T[i][j][0]<tmin){
                tmin=T[i][j][0];
                tx=i;
                ty=j;
            }
        }
    }
    out<<tmin<<" "<<tx<<" "<<ty;
}
void write_ma(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<setw(4)<<T[i][j][1]<<" ";
        }
        cout<<"\n";
    }
}
int main(){
    read();
    solve();
    //write_ma();
    return 0;
}