Cod sursa(job #1732237)

Utilizator akaprosAna Kapros akapros Data 21 iulie 2016 11:22:18
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
#define maxN 152
#define mp make_pair
#define pii pair < int, int >
#define x first
#define y second
using namespace std;
int a[maxN][maxN], l, r, k, n, m;
bool vis[maxN][maxN], unlock[maxN * maxN];
int ans, cnt;
pii Q[maxN * maxN];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int okc(int x, int y)
{
    return (x > 0 && y > 0 && x <= n && y <= m);
}
void read()
{
    int i, j, x, y;
    freopen("castel.in", "r", stdin);
    scanf("%d %d %d", &n, &m, &k);
    cnt = 1;
    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
        scanf("%d", &a[i][j]);
    unlock[k] = 1;
    x = (k / m) + 1; y = k % m;
    if (y == 0)
        {
            -- x;
            y = m;
        }
    Q[++ r] = mp(x, y);
    vis[x][y] = 1;
}
void bfs()
{
    int d;
    while (l <= r)
    {
        pii nod = Q[++ l];
        for (d = 0; d < 4; ++ d)
            if (okc(nod.x + dx[d], nod.y + dy[d]) && unlock[a[nod.x + dx[d]][nod.y + dy[d]]] && !vis[nod.x + dx[d]][nod.y + dy[d]])
        {
            vis[nod.x + dx[d]][nod.y + dy[d]] = 1;
            unlock[(nod.x + dx[d] - 1) * m + nod.y + dy[d]] = 1;
            Q[++ r] = mp(nod.x + dx[d], nod.y + dy[d]);
            ++ cnt;
        }
    }
}
void solve()
{
    do
    {
        ans = cnt;
        int L = l;
        bfs();
        l = L;
    }while (ans != cnt);
}
void write()
{
    freopen("castel.out", "w", stdout);
    printf("%d\n", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}