Cod sursa(job #2303099)

Utilizator canmihaiCancescu Mihai canmihai Data 15 decembrie 2018 16:35:20
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,r,g,b,di[]={-1,1,0,0,-1,-1,1,1},dj[]={0,0,1,-1,-1,1,-1,1},dmin,sol=INT_MAX,rx,ry,jx,jy,c1,c2;
int distanter[150][150],distantej[150][150];
bool f[150][150];
char a[150][150],caracter;
struct nod{
    int x;
    int y;
    int d;
};
void bfs(int x, int y, int personaj){
    memset(f,false,sizeof f);
    queue<nod>coada;
    f[x][y]=true;dmin=-1;
    coada.push({x,y,1});
    while(!coada.empty()){
        nod curent=coada.front();
        coada.pop();
        int i=curent.x, j=curent.y, dist=curent.d;
      /*  if(i==finalx&&j==finaly){
            dmin=dist;cout<<dist;
           // cout<<dmin;
           // return 1;
            break;
        }*/
        if(personaj==1&&a[i][j]!='X')
            distanter[i][j]=dist;
        else
            distantej[i][j]=dist;
        for(int t=0;t<8;t++){
            int i2=i+di[t];
            int j2=j+dj[t];
            if(i2>0 && i2<=n && j2>0 && j2<=m && a[i2][j2]!='X'&&f[i2][j2]==0){
                f[i2][j2]=true;
              //  cout<<i2<<" "<<j2<<endl;
                coada.push({i2,j2,dist+1});
            }
        }
    }


}
int main(){
    fin>>n>>m>>noskipws>>a[0][0];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m+1;j++){
            fin>>noskipws>>caracter;
            if(caracter-'0'!=-38)
                a[i][j]=caracter;
            if(a[i][j]=='R'){
                rx=i;ry=j;
                //cout<<i<<" "<<j;
            }
            if(a[i][j]=='J'){
                jx=i;jy=j;
            }
        //    cout<<a[i][j]<<" "<<i<<" "<<j<<endl;
        }
       // cout<<endl;
    }
    bfs(rx,ry,1);
    bfs(jx,jy,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m+1;j++)
           if(distantej[i][j]==distanter[i][j]&&distantej[i][j]<sol&&distantej[i][j]!=0){
                c1=i;
                c2=j;
                sol=distantej[i][j];
        }
    fout<<sol<<" "<<c1<<" "<<c2;



    return 0;
}