Cod sursa(job #2147257)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 28 februarie 2018 16:39:01
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
#define N 102
short dx[8]={-1,0,1,0,1,-1,1,-1};
short dy[8]={0,-1,0,1,1,-1,-1,1};
int q[N*N][2];
short a[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]=-1; break;
                case 'R': x1=i, y1=j+1; a[i][j+1]=1; break;
                case 'J': x2=i, y2=j+1; a[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;
    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){
                if(a[c1][c2]+1==a[v1][v2]){
                    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;
                    }
                }
                else if(a[c1][c2]+1<a[v1][v2]){
                    a[v1][v2]=a[c1][c2]+1;
                    q[++u][0]=v1;
                    q[u][1]=v2;
                }
            }
        }
    }
    out<<minn<<" "<<m1<<" "<<m2;
    return 0;
}