Cod sursa(job #2447709)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 14 august 2019 12:57:50
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.47 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,v[1001][1001];
string c;
pair <int,int>marcat[1001][1001];

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;
            }
            else
            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;
        }
        if(!(v[i+1][j-1]) && !marcat[i+1][j-1].first && i+1<=n && 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>0 && 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();
    }

    i=xf;
    j=yf;
    ql.push(xf);
    qc.push(yf);
    marcat[xf][yf].second=1;
    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;
        }
        if(!(v[i+1][j-1]) && !marcat[i+1][j-1].second && i+1<=n && 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>0 && 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();
    }
    int cost=10e9;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(marcat[i][j].first==marcat[i][j].second && marcat[i][j].first && marcat[i][j].second<cost){
                    xs=i;
                    ys=j;
                    cost=marcat[i][j].first;
            }
        }
    }
    cout<<cost<<" "<<xs<<" "<<ys;
    return 0;
}