Cod sursa(job #2147444)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 28 februarie 2018 19:07:17
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
#define N 102
short dx[8]={-1,-1,0,1,1,1,0,-1};
short dy[8]={0,1,1,1,0,-1,-1,-1};
int q[N*N][2];
short a[N][N];
short b[N][N];
int main(){
    int n,m,i,j,x1,y1,x2,y2;
    string s;
    in>>n>>m;
    getline(in,s);
    for(i=1; i<=n; ++i){
        getline(in,s);
        for(j=0; j<m; ++j){
            switch(s[j]){
                case 'X': a[i][j+1]=b[i][j+1]=-1; break;
                case 'R': x1=i, y1=j+1; a[i][j+1]=1; break;
                case 'J': x2=i, y2=j+1; b[i][j+1]=1; break;
            }
        }
    }
    for(i=0; i<=n+1; ++i)
        a[i][m+1]=a[i][0]=-1;
    for(i=0; i<=m+1; ++i)
        a[n+1][i]=a[0][i]=-1;
    for(i=-1; i<=n+2; ++i)
        a[i][m+2]=a[i][-1]=-1;
    for(i=-1; i<=m+2; ++i)
        a[n+2][i]=a[-1][i]=-1;
    int u=0, p=0;
    q[++u][0]=x1;
    q[u][1]=y1;
    int c1,c2,v1,v2;
    while(p<=u){
        c1=q[++p][0];
        c2=q[p][1];
        for(i=0; i<8; ++i){
            v1=c1+dx[i];
            v2=c2+dy[i];
            if(a[v1][v2]==0){
                a[v1][v2]=a[c1][c2]+1;
                q[++u][0]=v1;
                q[u][1]=v2;
            }
        }
    }
    u=0, p=0;
    q[++u][0]=x2;
    q[u][1]=y2;
    int minn=1000000;
    int m1,m2;
    for(i=0; i<=n+1; ++i)
        b[i][m+1]=b[i][0]=-1;
    for(i=0; i<=m+1; ++i)
        b[n+1][i]=b[0][i]=-1;
    for(i=-1; i<=n+2; ++i)
        b[i][m+2]=b[i][-1]=-1;
    for(i=-1; i<=m+2; ++i)
        b[n+2][i]=b[-1][i]=-1;
    while(p<=u){
        c1=q[++p][0];
        c2=q[p][1];
        for(i=0; i<8; ++i){
            v1=c1+dx[i];
            v2=c2+dy[i];
            if(!b[v1][v2]){
                b[v1][v2]=b[c1][c2]+1;
                q[++u][0]=v1;
                q[u][1]=v2;
            }
            if(b[v1][v2]==a[v1][v2] && b[v1][v2]>0){
                if(minn>a[v1][v2])
                    minn=a[v1][v2], m1=v1, m2=v2;
                else if(minn==a[v1][v2]){
                    if(v1<m1)
                        minn=a[v1][v2], m1=v1, m2=v2;
                    else if(v1==m1)
                        if(v2<m2)
                            minn=a[v1][v2], m1=v1, m2=v2;
                }
            }

        }
    }
	out<<minn<<" "<<m1<<" "<<m2;
    return 0;
}