Cod sursa(job #2221135)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 13 iulie 2018 11:21:43
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.97 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
char s[103];
pair<int,int>x;
pair<pair<int,int>,int>x2;
queue<pair<pair<int,int>,int> >dq;
int n,m,i,j,v[101][101],t,l,v2[101][101],v3[101][101],l1,l2,c1,c2,c;
int main() {
    f>>n>>m;
    f.get();
    for(i=1; i<=n; i++) {
        f.getline(s,m+1);
        for(j=0; j<m; j++) {
            if(s[j]=='X') {
                v[i][j+1]=-1;
            } else if(s[j]=='R') {
                l1=i;
                c1=j+1;
            } else if(s[j]=='J') {
                l2=i;
                c2=j+1;
            }
        }
    }
    x=make_pair(l1,c1);
    x2=make_pair(x,0);
    dq.push(x2);
    while(!dq.empty()) {
        i=dq.front().first.first;
        j=dq.front().first.second;
        c=dq.front().second;
        c++;
        dq.pop();
        if((v2[i][j]==0 or v2[i][j]>c) && v[i][j]==0) {
            v2[i][j]=c;
            if(i>1) {
                x=make_pair(i-1,j);
                x2=make_pair(x,c);
                dq.push(x2);
                if(j>1) {
                    x=make_pair(i-1,j-1);
                    x2=make_pair(x,c);
                    dq.push(x2);
                }
                if(j<m) {
                    x=make_pair(i-1,j+1);
                    x2=make_pair(x,c);
                    dq.push(x2);
                }
            }
            if(i<n) {
                x=make_pair(i+1,j);
                x2=make_pair(x,c);
                dq.push(x2);
                if(j>1) {
                    x=make_pair(i+1,j-1);
                    x2=make_pair(x,c);
                    dq.push(x2);
                }
                if(j<m) {
                    x=make_pair(i+1,j+1);
                    x2=make_pair(x,c);
                    dq.push(x2);
                }
            }
            if(j>1) {
                x=make_pair(i,j-1);
                x2=make_pair(x,c);
                dq.push(x2);
            }
            if(j<m) {
                x=make_pair(i,j+1);
                x2=make_pair(x,c);
                dq.push(x2);
            }
        }
    }
    x=make_pair(l2,c2);
    x2=make_pair(x,0);
    dq.push(x2);
    while(!dq.empty()) {
        i=dq.front().first.first;
        j=dq.front().first.second;
        c=dq.front().second;
        c++;
        dq.pop();
        if((v3[i][j]==0 or v3[i][j]>c) && v[i][j]==0) {
            v3[i][j]=c;
            if(i>1) {
                x=make_pair(i-1,j);
                x2=make_pair(x,c);
                dq.push(x2);
                if(j>1) {
                    x=make_pair(i-1,j-1);
                    x2=make_pair(x,c);
                    dq.push(x2);
                }
                if(j<m) {
                    x=make_pair(i-1,j+1);
                    x2=make_pair(x,c);
                    dq.push(x2);
                }
            }
            if(i<n) {
                x=make_pair(i+1,j);
                x2=make_pair(x,c);
                dq.push(x2);
                if(j>1) {
                    x=make_pair(i+1,j-1);
                    x2=make_pair(x,c);
                    dq.push(x2);
                }
                if(j<m) {
                    x=make_pair(i+1,j+1);
                    x2=make_pair(x,c);
                    dq.push(x2);
                }
            }
            if(j>1) {
                x=make_pair(i,j-1);
                x2=make_pair(x,c);
                dq.push(x2);
            }
            if(j<m) {
                x=make_pair(i,j+1);
                x2=make_pair(x,c);
                dq.push(x2);
            }
        }
    }
    t=101*101;
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            if(v[i][j]==0 && v2[i][j]==v3[i][j] && v2[i][j]!=0 && t>v2[i][j])
            {
                t=v2[i][j];
                l=i;
                c=j;
            }
        }
    }
    g<<t<<" "<<l<<" "<<c;
    return 0;
}