Cod sursa(job #971625)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 9 iulie 2013 19:12:04
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

ifstream in ("castel.in");
ofstream out ("castel.out");

const int MAXN = 160;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int N, M;
queue <int> Q, Q2;
int A[MAXN][MAXN], X[MAXN][MAXN];
pair <int, int> Y[MAXN * MAXN];
bool Pos[MAXN * MAXN];
bool Viz[MAXN][MAXN];

bool ok (int x, int y)
{
    return (x >= 1 && x <= N && y >= 1 && y <= M);
}

int main()
{
    int K, i, j, now, nowx, nowy, vx, vy, v, Ans = 1;

    in >> N >> M >> K;
    now = 1;

    for (i = 1; i <= N; i ++)
        for (j = 1; j <= M; j ++)
            in >> A[i][j], Y[now] = make_pair (i, j), X[i][j] = now ++;

    Viz[Y[K].first][Y[K].second] = 1;
    Pos[K] = 1;
    Q.push (K);
    Q2.push (K);

    bool gasit = 1;
    while (gasit){
        gasit = 0;
        Q = Q2;

        while (!Q.empty ()){
            now = Q.front ();
            nowx = Y[now].first;
            nowy = Y[now].second;

            for (i = 0; i < 4; i ++){
                vx = nowx + dx[i];
                vy = nowy + dy[i];

                if (!ok (vx, vy))
                    continue;

                v = X[vx][vy];

                if (Pos[ A[vx][vy] ] && !Viz[vx][vy]){
                    Ans ++;
                    gasit = 1;
                    Pos[v] = 1;
                    Viz[vx][vy] = 1;
                    Q.push (v);
                    Q2.push (v);
                }
            }

            Q.pop ();
        }
    }

    out << Ans << "\n";

    return 0;
}