Cod sursa(job #3149863)

Utilizator The_SupremacySus Impostor The_Supremacy Data 13 septembrie 2023 10:55:34
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100;
int n,m;
int liber[NMAX+5][NMAX+5];
int dist[5][NMAX+5][NMAX+5];
queue<int>lin,col;
int dlin[10]={-1,-1,0,1,1,1,0,-1};
int dcol[10]={0,1,1,1,0,-1,-1,-1};
void BFS(int nr,int x,int y){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dist[nr][i][j]=INT_MAX;
        }
    }
    dist[nr][x][y]=1;
    lin.push(x);col.push(y);
    while(!lin.empty()){
        int i=lin.front(),j=col.front();
        lin.pop();col.pop();
        for(int k=0;k<8;k++){
            int i1=i+dlin[k],j1=j+dcol[k];
            if(i1>=1&&i1<=n&&j1>=1&&j1<=m&&liber[i1][j1]==0&&dist[nr][i1][j1]>dist[nr][i][j]+1){
                dist[nr][i1][j1]=dist[nr][i][j]+1;
                lin.push(i1);col.push(j1);
            }
        }
    }
}
int main()
{
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    fin>>n>>m;string s;getline(fin,s);
    int x1,x2,y1,y2;
    for(int i=1;i<=n;i++){
        getline(fin,s);
        for(int j=1;j<=m;j++){
            if(s[j-1]=='X'){
                liber[i][j]=1;
            }
            else if(s[j-1]=='R'){
                x1=i;y1=j;
            }
            else if(s[j-1]=='J'){
                x2=i;y2=j;
            }
        }
    }
    BFS(1,x1,y1);BFS(2,x2,y2);
    int min1=INT_MAX,l,c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dist[1][i][j]==dist[2][i][j]&&dist[1][i][j]<min1){
                min1=dist[1][i][j];l=i;c=j;
            }
        }
    }
    fout<<min1<<" "<<l<<" "<<c<<'\n';
    return 0;
}