Cod sursa(job #1836355)

Utilizator giotoPopescu Ioan gioto Data 28 decembrie 2016 12:09:44
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <cstdio>
using namespace std;

int l1, c1, Min = 2000000000, x1, y1, x2, y2, n, m, t[105][105], t2[105][105];
char s[105][105];
struct coada{
    int l, c;
}q[40005], z;
short dx[] = {0, 0, -1, 1};
short dy[] = {-1, 1, 0, 0};
inline void BFS(){
    int st = 1, dr = 1;
    q[1].l = x1; q[1].c = y1;
    t[x1][y1] = 0;
    while(st <= dr){
        z = q[st++];
        for(short k = 0; k < 4 ; ++k){
            int x = dx[k] + z.l;
            int y = dy[k] + z.c;
            if(x >= 1 && y >= 0 && x <= n && y < m && s[x][y] != 'X'){
                if(t[x][y] > t[z.l][z.c] + 1){
                    t[x][y] = t[z.l][z.c] + 1;
                    q[++dr].l = x; q[dr].c = y;
                }
            }
        }
    }
}
inline void BFS2(){
    int st = 1, dr = 1;
    q[1].l = x2; q[1].c = y2;
    t2[x2][y2] = 0;
    while(st <= dr){
        z = q[st++];
        for(short k = 0; k < 4 ; ++k){
            int x = dx[k] + z.l;
            int y = dy[k] + z.c;
            if(x >= 1 && y >= 0 && x <= n && y < m && s[x][y] != 'X'){
                if(t2[x][y] > t2[z.l][z.c] + 1){
                    t2[x][y] = t2[z.l][z.c] + 1;
                    q[++dr].l = x; q[dr].c = y;
                    if(t2[x][y] == t[x][y])
                        if(t2[x][y] < Min)
                            {l1 = x; Min = t2[x][y]; c1 = y;}
                        else if(Min == t2[x][y] && y < c1)
                            l1 = x, c1 = y;
                }
            }
        }
    }
}
int main(){
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    scanf("%d%d\n", &n, &m);
    for(int i = 1; i <= n ; ++i){
        fgets(s[i], 101, stdin);
        for(int j = 0; j < m ; ++j){
            t[i][j] = 2000000000;
            t2[i][j] = 2000000000;
            if(s[i][j] == 'R') x1 = i, y1 = j;
            else if(s[i][j] == 'J') x2 = i, y2 = j;
        }
    }
    BFS();
    BFS2();
    printf("%d %d %d", Min, l1, c1 + 1);
    return 0;
}