Cod sursa(job #829806)

Utilizator NewBeginningNewBeginning NewBeginning Data 5 decembrie 2012 21:19:14
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <queue>

using namespace std;

const int NMAX = 105;
const int MMAX = 105;

const char IN[] = "rj.in";
const char OUT[] = "rj.out";

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

int A[NMAX][NMAX];
char T[NMAX][NMAX];

int N, M;
int tmin, pozx, pozy;

queue<int> X, Y;

void BFS() {
    int x, y, k;
    while(!X.empty()) {
        x = X.front();
        y = Y.front();
        X.pop();
        Y.pop();

        for(k = 0; k < 8; ++ k) {
            if(A[x + dx[k]][y + dy[k]] == -1) continue;

            if(!A[x + dx[k]][y + dy[k]]) {
                T[x + dx[k]][y + dy[k]] = T[x][y];
                A[x + dx[k]][y + dy[k]] = A[x][y] - 1;
                X.push(x + dx[k]);
                Y.push(y + dy[k]);
            }
            else if(T[x + dx[k]][y + dy[k]] != T[x][y]) {
                tmin = A[x + dx[k]][y + dy[k]];
                pozx = x + dx[k];
                pozy = y + dy[k];
                return;
            }
        }
    }
}

int main() {
    int i, j;
    char C;

    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);

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

    for(i = 0; i <= N; ++i) A[0][i] = A[i][0] = -1;
    for(i = 0; i <= N; ++i) A[i][M + 1] = A[N + 1][i] = -1;

    i = j = 1;

    while((C = fgetc(stdin)) != EOF) {
        if(C == '\n') continue;
        if(C == 'X') A[i][j] = -1;
        if(C == 'R') A[i][j] = -1, T[i][j] = 1, X.push(i), Y.push(j);
        if(C == 'J') A[i][j] = -1, T[i][j] = 2, X.push(i), Y.push(j);
        ++j;
        if(j == M + 1) j = 1, ++i;
    }

    BFS();

    printf("%d %d %d", -tmin, pozx, pozy);

    return 0;
}