Cod sursa(job #829869)

Utilizator NewBeginningNewBeginning NewBeginning Data 5 decembrie 2012 22:19:11
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <cstdio>
#include <queue>
#define INF (1 << 20)

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;

    pozx = INF;
    pozy = INF;

    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] && x + dx[k] <= pozx && y + dy[k] <= pozy) {
                tmin = A[x + dx[k]][y + dy[k]];
                pozx = x + dx[k];
                pozy = y + dy[k];
                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;
}