Cod sursa(job #1564605)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 9 ianuarie 2016 20:01:45
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

const int total = 150 * 150 + 10;

int n , m , k , i , j , ans;
int node , node2;
int a[total] , Move[5];
bool ap[total];

vector < int > wait[total];
deque < int > dq;

bool ok(int node)
{
    return (1 <= node && node <= n * m);
}

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

    scanf("%d %d %d", &n, &m, &k);
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            scanf("%d", &a[(i-1)*m+j]);

    Move[1] = -1; Move[2] = 1; Move[3] = -m; Move[4] = m;

    dq.push_back(k);
    while (dq.size())
    {
        ans++;

        node = dq.front(); ap[node] = 1; dq.pop_front();
        for (auto &it : wait[node])
            if (!ap[it])
                ap[it] = 1, dq.push_back(it);

        for (int dir = 1; dir <= 4; ++dir)
        {
            node2 = node + Move[dir];
            if (ok(node2) && !ap[node2] && ap[a[node2]])
                ap[node2] = 1, dq.push_back(node2);
            else if (ok(node2) && !ap[node2])
                wait[a[node2]].push_back(node2);
        }
    }

    printf("%d\n", ans);

    return 0;
}