Cod sursa(job #2542517)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 10 februarie 2020 08:44:43
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.74 kb
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

queue < pair < int , int > > q;
int n,m;
int mat[105][105];
char sir[105];
int adiac1[105][105];
int adiac2[105][105];
int linrom,colrom,linjul,coljul;
int dx[5]={0,-1,0,1,0}, dy[5]={0,0,1,0,-1};
int lin,col;
int dist;
void bordare() {
for (int i=1;i<=n;i++) {
    mat[i][0]=-1;
    mat[i][m+1]=-1;
}
for (int j=1;j<=m;j++) {
    mat[0][j]=-1;
    mat[n+1][j]=-1;
}
}

void lee1() {
 while (q.empty()==0) {
    lin = q.front().first;
    col= q.front().second;
    for (int k=1;k<=4;k++) {
        if (mat[lin+dx[k]][col+dy[k]]==0 && (adiac1[lin+dx[k]][col+dy[k]]>adiac1[lin][col]+1 || adiac1[lin+dx[k]][col+dy[k]]==0)) {
            adiac1[lin+dx[k]][col+dy[k]]=adiac1[lin][col]+1;
            q.push(make_pair(lin+dx[k],col+dy[k]));
        }
    }
    q.pop();
 }
}


void lee2() {
 while (q.empty()==0) {
    lin = q.front().first;
    col= q.front().second;
    for (int k=1;k<=4;k++) {
        if (mat[lin+dx[k]][col+dy[k]]==0 && (adiac2[lin+dx[k]][col+dy[k]]>adiac2[lin][col]+1 || adiac2[lin+dx[k]][col+dy[k]]==0)) {
            adiac2[lin+dx[k]][col+dy[k]]=adiac2[lin][col]+1;
            q.push(make_pair(lin+dx[k],col+dy[k]));
        }
    }
    q.pop();
 }
}

int main()
{
    f >> n >> m;
    f.get();
    bordare();
    for (int i=1;i<=n;i++) {
        f.getline(sir,100);
        for (int j=0;j<strlen(sir);j++) {
            if (sir[j]==' ') {
                mat[i][j+1]=0;
            }
            else if (sir[j]=='X') {
                mat[i][j+1]=-1;
            }
            else if (sir[j]=='R') {
                linrom=i;
                colrom=j+1;
                mat[i][j+1]=0;
            }
            else if(sir[j]=='J') {
                linjul=i;
                coljul=j+1;
                mat[i][j+1]=0;
            }
        }
    }
    q.push(make_pair(linjul,coljul));
    adiac1[linjul][coljul]=1;
    lee1();
    q.push(make_pair(linrom,colrom));
    adiac2[linrom][colrom]=1;
    lee2();
    /*for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            g << mat[i][j];
        }
        g <<'\n';
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            g << adiac1[i][j];
        }
        g <<'\n';
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            g << adiac2[i][j];
        }
        g <<'\n';
    }
    g << linjul <<" "<<coljul<<"   "<<linrom<<" "<<colrom<<" " <<adiac1[linrom][colrom];
*/
     /*dist = adiac1[linrom][colrom]+1;
     dist/=2;
     int ok=0;
     for (int i=1;i<=n && ok==0;i++) {
        for (int j=1;j<=m && ok==0;j++) {
            if (adiac1[i][j]==dist && adiac2[i][j]==dist) {
                g << dist-1 <<" " << i <<" "<< j;
                ok=1;
            }
        }
     }
     */
     dist=adiac1[linrom][colrom];
     if (dist&2==1) {
        dist++;
        dist/=2;
        int ok=0;
         for (int i=1;i<=n && ok==0;i++) {
            for (int j=1;j<=m && ok==0;j++) {
                if (adiac1[i][j]==dist && adiac2[i][j]==dist) {
                    g << dist-1 <<" " << i <<" "<< j;
                    ok=1;
                }
            }
         }
     }
     else {
        int dist1=((dist+1)/2)+1;
        int dist2=((dist+1)/2);
        int ok=0;
        for (int i=1;i<=n && ok==0;i++) {
            for (int j=1;j<=m && ok==0;j++) {
                if ((adiac1[i][j]==dist1 && adiac2[i][j]==dist2) || (adiac1[i][j]==dist2 && adiac2[i][j]==dist1)) {
                    g << dist2-1 <<" " << i <<" "<< j;
                    ok=1;
                }
            }
         }
     }


    return 0;
}