Cod sursa(job #2957212)

Utilizator AswVwsACamburu Luca AswVwsA Data 21 decembrie 2022 22:58:11
Problema Castel Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
//Sepultura rupe
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#define ll long long
using namespace std;

const int NMAX = 150;

int di[] = {-1, 1, 0, 0};
int dj[] = {0, 0, -1, 1};

int v[NMAX + 1][NMAX + 1];

vector <int> g[NMAX * NMAX + 1];
bool viz[NMAX * NMAX + 1];

bool ok[NMAX + 1][NMAX + 1];
bool seen[NMAX + 1][NMAX + 1];
int n, m;
void dfs1(int nod)
{
    viz[nod] = 1;
    int col = nod % m;
    if (col == 0)
        col = m;
    ok[nod / m + bool(nod % m)][col] = 1;
    for (int u : g[nod])
        if (!viz[u])
        {
            dfs1(u);
        }
}
int cnt;
void dfs2(int i, int j)
{
    seen[i][j] = 1;
    cnt++;
    for (int k = 0; k < 4; k++)
    {
        int ni = i + di[k];
        int nj = j + dj[k];
        if (ni >= 1 and ni <= n and nj >= 1 and nj <= m and !seen[ni][nj] and ok[ni][nj])
        {
            dfs2(ni, nj);
        }
    }
}
int main()
{
    ifstream cin("castel.in");
    ofstream cout("castel.out");
    int k, i, j;
    cin >> n >> m >> k;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            cin >> v[i][j];
            g[(i - 1) * m + j].push_back(v[i][j]);
            g[v[i][j]].push_back((i - 1) * m + j);
        }
    dfs1(k);
    int col = k % m;
    if (col == 0)
        col = m;
    dfs2(k / m + bool(k % m), col);
    cout << cnt;
}