Cod sursa(job #2480138)

Utilizator DavidLDavid Lauran DavidL Data 24 octombrie 2019 22:48:55
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("castel.in");
ofstream fo("castel.out");
#define cin fi
#define cout fo

const int NMAX = 160;
const int dl[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};

int m, n, k;
int M[NMAX][NMAX];
bool viz[NMAX][NMAX];
bool am[NMAX][NMAX];
vector < pair<int, int> > careAu[NMAX][NMAX];

inline bool val(int l, int c)
{
    return 1 <= l && l <= m && 1 <= c && c <= n;
}

pair <int, int> getPoz(int k)
{
    int lin = k / n + (k % n != 0);
    int col = k - (lin - 1) * n;

    return make_pair(lin, col);
}

int nrVeciniVizitati(int lin, int col)
{
    int ret = 0;
    for (int d = 0; d < 4; d++)
    {
        int ln = lin + dl[d], cn = col + dc[d];
        if (val(ln, cn) && viz[ln][cn])
            ret++;
    }
    return ret;
}
/*
bool oriceViz(int lin, int col)
{
    for (int i = 0; i <= 4; i++)
        if (viz[i][lin][col])
            return 1;
    return 0;
}*/

void faLee()
{
    queue < pair<int, int> > Q;
    int lin = getPoz(k).first, col = getPoz(k).second;

    viz[lin][col] = 1;

    Q.push({lin, col});

    while (!Q.empty())
    {
        lin = Q.front().first, col = Q.front().second;
        Q.pop();

        //cout << lin << " " << col << "\n";

        viz[lin][col] = 1;

        for (int d = 0; d < 4; d++)
        {
            int ln = lin + dl[d], cn = col + dc[d];
            if (val(ln, cn) && viz[getPoz(M[ln][cn]).first][getPoz(M[ln][cn]).second] && !viz[ln][cn])
            {
                Q.push({ln, cn});
                viz[ln][cn] = 1;
            }
        }

        for (auto x: careAu[lin][col])
            if (!viz[x.first][x.second] && nrVeciniVizitati(x.first, x.second))
                Q.push(x);
    }
    
}

int main()
{
    cin >> m >> n >> k;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> M[i][j];
            careAu[getPoz(M[i][j]).first][getPoz(M[i][j]).second].push_back({i, j});
        }

    if (M[getPoz(k).first][getPoz(k).second] != k)
    {
        cout << 0;
        return 0;
    }
            
    faLee();

    int rez = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (viz[i][j])
                rez++;
    cout << rez;

    return 0;
}