Cod sursa(job #1153928)

Utilizator SmarandaMaria Pandele Smaranda Data 25 martie 2014 20:52:35
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 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], a [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", &a [i][j]);
            key [i][j] = ++ u;
            if (u == k) {
                start.x = i;
                start.y = j;
            }
        }
}

void solve () {
    POS temp, temp2;
    long i, xx, yy, xn, yn;
    vector <POS> :: iterator it;

    q.push (start);
    been [start.x][start.y] = 1;
    while (!q.empty ()) {
        temp = q.front ();
        num ++;
        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;
            }
        }
        for (i = 0; i < 4; i ++) {
            xn = temp.x + dx [i];
            yn = temp.y + dy [i];
            temp2.x = xn;
            temp2.y = yn;
            if (xn >= 1 && xn <= n && yn >= 1 && yn <= m && been [xn][yn] == 0) {
                k = a [xn][yn];
                xx = k / m + 1;
                yy = k % m;
                if (yy == 0) {
                    yy = m;
                    xx -= 1;
                }
                if (been [xx][yy] == 1) {
                    been [xn][yn] = 1;
                    q.push (temp2);
                }
                else
                    waiting [k].push_back (temp2);
            }
        }
        q.pop ();
    }
    printf ("%ld\n", num);
}

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

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