Cod sursa(job #1598775)

Utilizator dsergiu05Sergiu Druga dsergiu05 Data 13 februarie 2016 12:28:50
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

const int nd=8;
const int dx[8]={1, -1, 0, 0, 1, -1, -1, 1}, dy[8]={0, 0, 1 ,-1, 1, 1,-1, -1};
const int inf=1e9;
const int nmax=100;

int v[nmax+2][nmax+2];
short int qx[nmax*nmax+1],qy[nmax*nmax+1];
int qb=1,qe=0;

int abs(int x) {
    if (x<0) {
        return -x;
    } else {
        return x;
    }
}

int main () {
    string s;
    int n,m;
    fin>>n>>m;
    getline( fin, s);

    int x1,x2,y1,y2;
    for (int i=1; i<=n; i++){
        getline( fin, s);
        for (int j=0; j<(int)s.size(); j++){
            if (s[j]=='R') {
                x1=i;
                y1=j+1;
                v[i][j+1]=1;
            } else if (s[j]=='J') {
                x2=i;
                y2=j+1;
                v[i][j+1]=-1;
            } else if (s[j]=='X') {
                v[i][j+1]=inf;
            }
        }
    }

    for (int i=0; i<=n+1; i++) {
        v[0][i]=inf;
        v[n+1][i]=inf;
    }
    for (int i=0; i<=m+1; i++) {
        v[i][0]=inf;
        v[i][m+1]=inf;
    }

    qe++;
    qx[qe]=x1;
    qy[qe]=y1;
    qe++;
    qx[qe]=x2;
    qy[qe]=y2;
    while (qb<=qe) {
        int x=qx[qb], y=qy[qb];
        qb++;
        for (int i=0; i<nd; i++) {
            int xn=x+dx[i],yn=y+dy[i];
            if (v[xn][yn]==0) {
                qe++;
                qx[qe]=xn;
                qy[qe]=yn;
                if (v[x][y]>0) {
                    v[xn][yn]=v[x][y]+1;
                } else {
                    v[xn][yn]=v[x][y]-1;
                }
            }
        }
    }
    int sol=inf, solx, soly;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            for (int k=0; k<nd; k++) {
                int in=i+dx[k], jn=j+dy[k];
                if (v[in][jn]!=inf && v[i][j]!=inf && v[in][jn]*v[i][j]<0) {
                    if (abs(v[in][jn])+1<sol) {
                        sol=abs(v[in][jn])+1;
                        solx=i;
                        soly=j;
                    }
                }
            }
        }
    }
    fout<<sol<<" "<<solx<<" "<<soly<<"\n";

    return 0;
}