Cod sursa(job #2251690)

Utilizator AlexandruPaulSirbu Alex AlexandruPaul Data 1 octombrie 2018 20:55:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
const int Maxx=1e2+1;
const int INF=(1<<30);
const int dx[]={-1,-1,-1,0,0,1,1,1},
          dy[]={-1,0,1,-1,1,-1,0,1};
struct edge{
    int x,y;
}nw,ac,jul,rom;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,i,j,m;
string A;
int ans_lin,ans_col,ans_t=INF;
int mat[2][Maxx][Maxx];
void bfs(edge from,edge to,bool flip);
bool test(edge nw);
int main() {
    fin>>n>>m;
    getline(fin,A);
    for (i=1;i<=n;++i){
        getline(fin,A);
        for (j=0;j<m;++j){
            if (A[j]=='R') rom.x=i,rom.y=j+1;
            if (A[j]=='J') jul.x=i,jul.y=j+1;
            if (A[j]=='X') mat[0][i][j+1]=mat[1][i][j+1]=-1;
        }
    }
    bfs(rom,jul,0);
    bfs(jul,rom,1);
    for (i=1;i<=n;++i){
        for (j=1;j<=m;++j){
            if (mat[0][i][j]==mat[1][i][j] && ans_t>mat[0][i][j] && mat[0][i][j]>0){
                ans_t=mat[0][i][j];
                ans_lin=i;
                ans_col=j;
            }
        }
    }
    fout<<ans_t<<" "<<ans_lin<<" "<<ans_col;
    return 0;
}
void bfs(edge from,edge to,bool flip){
    deque <edge> Q;
    Q.push_back(from);
    mat[flip][from.x][from.y]=1;
    while(!Q.empty() && mat[flip][to.x][to.y]==0){
        ac=Q.front();
        Q.pop_front();
        for (int i=0;i<8;++i){
            nw.x=ac.x+dx[i];
            nw.y=ac.y+dy[i];
            if (test(nw) && mat[flip][nw.x][nw.y]==0){
                Q.push_back(nw);
                mat[flip][nw.x][nw.y]=1+mat[flip][ac.x][ac.y];
            }
        }
    }
}
bool test(edge nw){
    return nw.x>0 && nw.y>0 && nw.x<=n && nw.y<=m;
}