Cod sursa(job #1875602)

Utilizator raluca1234Tudor Raluca raluca1234 Data 11 februarie 2017 12:55:33
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>

#define maxN 100
#define maxM 100

#define INF 0x3f3f3f3f

using namespace std;

const int dx[]={-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[]={0, 1, 1, 1, 0, -1, -1, -1};

int N, M, m[maxN+1][maxM+1], t[2][maxN+1][maxM+1];
struct POINT{
    int x, y;
};
POINT q[maxN*maxM+1];

void BFS(POINT p, int c){
    int prim, ultim, d;
    POINT pn;
    prim=ultim=1;
    q[1]=p;
    m[p.x][p.y]=1;
    t[c][p.x][p.y]=1;
    while (prim<=ultim){
        for (d=0; d<8; d++){
            pn.x=q[prim].x+dx[d];
            pn.y=q[prim].y+dy[d];
            if (pn.x>=1 && pn.x<=N && pn.y>=1 && pn.y<=M)
                if (m[pn.x][pn.y]==0){
                    t[c][pn.x][pn.y]=t[c][q[prim].x][q[prim].y]+1;
                    m[pn.x][pn.y]=1;
                    ultim++;
                    q[ultim]=pn;
                }
        }
        prim++;
    }
}

int main(){
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    int i, j, tmin;
    char ch;
    POINT R, J, ans;

    scanf("%d%d\n", &N, &M);

    for (i=1; i<=N; i++){
        for (j=1; j<=M; j++){
            ch=getchar();
            if (ch=='X') m[i][j]=-1;
            if (ch=='R'){
                R.x=i; R.y=j;
            }
            if (ch=='J'){
                J.x=i; J.y=j;
            }
        }
        ch=getchar();
    }
    BFS(R, 0);

    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
            if (m[i][j]==1) m[i][j]=0;

    BFS(J, 1);

    tmin=INF;
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
            if (t[0][i][j]==t[1][i][j] && t[0][i][j]!=0)
                if (t[0][i][j]<tmin){
                    tmin=t[0][i][j];
                    ans.x=i;
                    ans.y=j;
                }
    printf("%d %d %d\n", tmin, ans.x, ans.y);
    return 0;
}