Cod sursa(job #1153910)

Utilizator SmarandaMaria Pandele Smaranda Data 25 martie 2014 20:36:29
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

struct POS {
    long x, y;
};

const long N = 155, M = 155;
POS start;
long n, m, k, key [N][M], num = 0, been [N][M];
long dx [] = {-1, 0, 1, 0}, dy [] = {0, 1, 0, -1};
bool  used [N][M];
queue <POS> q;
vector <POS> waiting [22506];

void read () {
    long i, j, u = 0, t;
    POS temp;

    scanf ("%ld%ld%ld", &n, &m, &k);
    for (i = 1; i <= n; i ++)
        for (j = 1; j <= m; j ++) {
            scanf ("%ld", &t);
            temp.x = i;
            temp.y = j;
            waiting [t].push_back (temp);
            key [i][j] = ++ u;
            if (u == k) {
                start.x = i;
                start.y = j;
            }
        }
}

void fill (long x, long y) {
    long xn, yn, i;
    num ++;
    used [x][y] = 1;
    for (i = 0; i < 4; i ++) {
        xn = x + dx [i];
        yn = y + dy [i];
        if (xn >= 1 && xn <= n && yn >= 1 && yn <= m && been [xn][yn] == 1 && !used [xn][yn])
            fill (xn, yn);
    }
}

void solve () {
    POS temp;
    long i;
    vector <POS> :: iterator it;

    q.push (start);
    been [start.x][start.y] = 1;
    while (!q.empty ()) {
        temp = q.front ();
        k = key [temp.x][temp.y];
        for (it = waiting [k].begin (); it != waiting [k].end (); ++ it) {
            if (!been [(*it).x][(*it).y]) {
                q.push (*it);
                been [(*it).x][(*it).y] = 1;
            }
        }
        q.pop ();
    }
    fill (start.x, start.y);
    printf ("%ld\n", num);
}

int main () {
    freopen ("castel.in", "r", stdin);
    freopen ("castel.out", "w", stdout);

    read ();
    solve ();
    return 0;
}