Cod sursa(job #2781212)

Utilizator tomaionutIDorando tomaionut Data 8 octombrie 2021 18:58:43
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");
int n, m, k,sol;
int a[155][155],t;
pair <int, int> b[22600];
bool vis[22600],key[22600];
vector <int> v[22600];
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
queue<int> q;
bool OK(int i, int j)
{
    return (1 <= i and i <= n and 1 <= j and j <= m);
}
int cod(int x, int y)
{
    return (x - 1) * m + y;
}
int main()
{
    int i, j,x,d,y;
    fin >> n >> m >> k;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            fin >> a[i][j];
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            b[++t] = { i,j };
    q.push(k);
    vis[k] = key[k] = 1;
    while (!q.empty())
    {
        x = q.front();
        key[x] = 1;
        for (auto w : v[x])
            if (vis[w] == 0)
            {
                q.push(w);
                vis[w] = 1;
            }
        i = b[x].first;
        j = b[x].second;
        for (d = 0; d <= 3; d++)
        {
            x = i + dx[d];
            y = j + dy[d];
            if (OK(x, y) and vis[(cod(x, y))] == 0)
            {
                if (key[a[x][y]] == 1)
                {
                    q.push(cod(x, y));
                    vis[cod(x, y)] = 1;
                }
                else v[a[x][y]].push_back(cod(x, y));
            }
        }
        q.pop();
    }
    for (i = 1; i <= n * m; i++)
        sol += vis[i];
    fout << sol;


    return 0;
    
}