Cod sursa(job #829865)

Utilizator NewBeginningNewBeginning NewBeginning Data 5 decembrie 2012 22:15:01
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 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] && A[x + dx[k]][y + dy[k]] == A[x][y] + 1) {
                tmin = A[x + dx[k]][y + dy[k]];
                pozx = x;
                pozy = y;
                return;
            }
        }
    }
}

int main() {
    int i, j, count = 0;
    char c = ' ';

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

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

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

    i = j = 1;

    fgetc(stdin);

    while((c = fgetc(stdin)) != EOF) {
        if(i == N + 1 && j == M + 1) break;

        if(c == '\n') {
            ++i;
            j = 1;
            continue;
        }

        if(c == 'X') A[i][j] = -1;
        if(c == 'R') T[i][j] = 1, A[i][j] = -1, X.push(i), Y.push(j);
        if(c == 'J') T[i][j] = 2, A[i][j] = -1, X.push(i), Y.push(j);

        ++j;
    }

    BFS();

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

    return 0;
}