Cod sursa(job #517633)

Utilizator nandoLicker Nandor nando Data 29 decembrie 2010 13:28:08
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>
#include <bitset>
#include <vector>
using namespace std;

FILE* fin = fopen ("castel.in", "r");
FILE* fout = fopen ("castel.out", "w");

#define MAXN 160
#define MAXV (MAXN * MAXN)

int n, m, k;
int q[MAXV], prev[MAXV], lsp = 0;
bitset<MAXV> viz;
vector<int> lst[MAXV];

typedef vector<int>::iterator iter;

const int dir[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

inline bool onMap (int x, int y)
{
    return (1 <= x && x <= n) && (1 <= y && y <= m);
}

int main()
{
    fscanf (fin, "%d %d %d\n", &n, &m, &k);

    for (int i = 1; i <= n * m; ++i) {
        fscanf (fin, "%d ", &prev[i]);
    }

    int nr = 1;
    q[0] = k;
    viz[k] = true;

    int x, y, nx, ny, idx;
    for (int beg = 0, end = 1; beg < end; ++beg) {
        for (iter it = lst[q[beg]].begin(); it != lst[q[beg]].end(); ++it) {
            if(!viz[*it]){
                viz[*it] = true;
                ++nr;
                q[end++] = *it;
            }
        }

        x = (q[beg] - 1) / m + 1;
        y = (q[beg] - 1) % m + 1;

        for (int i = 0; i < 4; ++i) {
            nx = x + dir[i][0], ny = y + dir[i][1];
            if (onMap (nx, ny)) {
                idx = (nx - 1) * m + ny;

                if (!viz[idx]) {
                    if (viz[prev[idx]]) {
                        q[end++] = idx;
                        viz[idx] = true;
                        ++nr;
                    } else {
                        lst[prev[idx]].push_back(idx);
                    }
                }
            }
        }
    }

    fprintf (fout, "%d\n", nr);

    fclose (fin);
    fclose (fout);
    return 0;
}