Cod sursa(job #901497)

Utilizator swim406Teudan Adina swim406 Data 1 martie 2013 10:27:22
Problema Castel Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#include <queue>

using namespace std;

queue < pair < int, int > > q;

int main() {
    freopen ("castel.in", "r", stdin);
    freopen ("castel.out", "w", stdout);
    int M, N, K, i, j, a[151][151], count[151][151], k = 0, keys[151*151], c = 0, x, y, x1, y1, viz[151][151];
    scanf ("%d %d %d", &M, &N, &K);
    for (i = 1; i <= M * N; ++i)
        keys[i] = 0;
    for (i = 1; i <= M; ++i)
        for (j = 1; j <= N; ++j) {
            ++k;
            viz[i][j] = 0;
            scanf ("%d", &a[i][j]);
            count[i][j] = k;
            if (k == K) {
                q.push(make_pair(i,j));
                ++c;
                keys[k] = 1;
                viz[i][j] = 1;
            }
        }
    int dx[4] = {1,0,0,-1};
    int dy[4] = {0,-1,1,0};
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (i = 0; i < 4; ++i) {
            x1 = x + dx[i];
            y1 = y + dy[i];
            if (x1 >= 1 && x1 <= M && y1 >= 1 && y1 <= N) {
                if (keys[a[x1][y1]] && viz[x1][y1] <= N) {
                    q.push (make_pair(x1, y1));
                    viz[x1][y1]++;
                    if (!keys[count[x1][y1]]) {
                        ++c;
                        keys[count[x1][y1]] = 1;
                    }
                }
            }
        }
    }
    printf ("%d\n", c);
    return 0;
}