Cod sursa(job #994829)

Utilizator primulDarie Sergiu primul Data 6 septembrie 2013 14:12:20
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 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;
}