Cod sursa(job #2447194)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 12 august 2019 13:41:43
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.76 kb
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

ifstream cin("rj.in");
ofstream cout("rj.out");

queue<int>ql,qc;
int n,m,xs,ys,xf,yf,x,y,cost=10e9,v[1001][1001];
pair<int,int>marcat[1001][1001];
string c;

int main()
{
    cin>>n>>m;
    cin.get();
    for(int i=1;i<=n;i++){
            getline(cin,c);
        for(int j=0;j<m;j++){
            if(c[j]=='X')
                v[i][j+1]=1;
            else
                v[i][j+1]=0;
            if((c[j]=='R'||c[j]=='J') && !xs){
                xs=i;
                ys=j+1;
            }
            if((c[j]=='R'||c[j]=='J') && xs){
                xf=i;
                yf=j+1;
            }
        }
    }
    int i=xs;
    int j=ys;
    ql.push(xs);
    qc.push(ys);
    marcat[xs][ys].first = 1;
    while(!ql.empty()){
        i=ql.front();
        j=qc.front();
        if(!(v[i][j+1]) && !marcat[i][j+1].first && j+1<=m){
            ql.push(i);
            qc.push(j+1);
            marcat[i][j+1].first=marcat[i][j].first+1;
        }
        if(!(v[i][j-1]) && !marcat[i][j-1].first && j-1>0){
            ql.push(i);
            qc.push(j-1);
            marcat[i][j-1].first=marcat[i][j].first+1;
        }
        if(!(v[i+1][j]) && !marcat[i+1][j].first && i+1<=n){
            ql.push(i+1);
            qc.push(j);
            marcat[i+1][j].first=marcat[i][j].first+1;
        }
        if(!(v[i-1][j]) && !marcat[i-1][j].first && i-1>0){
            ql.push(i-1);
            qc.push(j);
            marcat[i-1][j].first=marcat[i][j].first+1;
        }
        if(!(v[i-1][j-1]) && !marcat[i-1][j-1].first && i-1>0 && j-1>0){
            ql.push(i-1);
            qc.push(j-1);
            marcat[i-1][j-1].first=marcat[i][j].first+1;
        }
        if(!(v[i+1][j+1]) && !marcat[i+1][j+1].first && i+1<=n && j+1<=m){
            ql.push(i+1);
            qc.push(j+1);
            marcat[i+1][j+1].first=marcat[i][j].first+1;
        }
        ql.pop();
        qc.pop();
    }
    marcat[xf][yf].second=1;
    i=xf;
    j=yf;
    ql.push(xf);
    qc.push(yf);
    while(!ql.empty()){
        i=ql.front();
        j=qc.front();
        if(!(v[i][j+1]) && !marcat[i][j+1].second && j+1<=m){
            ql.push(i);
            qc.push(j+1);
            marcat[i][j+1].second=marcat[i][j].second+1;
        }
        if(!(v[i][j-1]) && !marcat[i][j-1].second && j-1>0){
            ql.push(i);
            qc.push(j-1);
            marcat[i][j-1].second=marcat[i][j].second+1;
        }
        if(!(v[i+1][j]) && !marcat[i+1][j].second && i+1<=n){
            ql.push(i+1);
            qc.push(j);
            marcat[i+1][j].second=marcat[i][j].second+1;
        }
        if(!(v[i-1][j]) && !marcat[i-1][j].second && i-1>0){
            ql.push(i-1);
            qc.push(j);
            marcat[i-1][j].second=marcat[i][j].second+1;
        }
        if(!(v[i-1][j-1]) && !marcat[i-1][j-1].second && i-1>0 && j-1>0){
            ql.push(i-1);
            qc.push(j-1);
            marcat[i-1][j-1].second=marcat[i][j].second+1;
        }
        if(!(v[i+1][j+1]) && !marcat[i+1][j+1].second && i+1<=n && j+1<=m){
            ql.push(i+1);
            qc.push(j+1);
            marcat[i+1][j+1].second=marcat[i][j].second+1;
        }
        ql.pop();
        qc.pop();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){

            if(v[i][j]==0 and marcat[i][j].second > 0 and marcat[i][j].first > 0 ){
                cost=min(cost,max(marcat[i][j].first,marcat[i][j].second));
                if (max(marcat[i][j].first,marcat[i][j].second)==cost){
                    x=i;
                    y=j;
                }
            }
        }

    }
    cout<<cost<<" "<<x<<" "<<y;
    return 0;
}