Cod sursa(job #2566348)

Utilizator pregoliStana Andrei pregoli Data 2 martie 2020 20:41:16
Problema Castel Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
///****************************

const int NMAX = 155;
int a[NMAX][NMAX];
bool vis[NMAX][NMAX], have[NMAX * NMAX];
vector<pair<int, int> > rooms[NMAX * NMAX];//keys[i]- rooms(coord) which can be opened using key i;(locked)
int startI, startJ;
int n, m, k;

void read()
{
    fin >> n >> m >> k;
    for (int val = 0, i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            fin >> a[i][j];
            if (++val == k)
            {
                startI = i;
                startJ = j;
            }
        }
}

int getKey(int i, int j)
{
    return m * (i - 1) + j;
}

bool isInside(int i, int j)
{
    return (i >= 1 && i <= n && j >= 1 && j <= m);
}

queue<pair<int, int> > q;
const short nd = 4, di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};
void Fill()
{
    q.push(make_pair(startI, startJ));
    while (!q.empty())
    {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        int key = getKey(i, j);

        while (!rooms[key].empty() && 1)
        {
            int ii = rooms[key].back().first;
            int jj = rooms[key].back().second;
            rooms[key].pop_back();
            //if (1)
            {
                q.push(make_pair(ii, jj));
                vis[ii][jj] = true;
            }
        }

        vis[i][j] = true;
        have[key] = true;
        for (int dir = 0; dir < nd; dir++)
        {
            int nextI = i + di[dir];
            int nextJ = j + dj[dir];
            if (isInside(nextI, nextJ) && !vis[nextI][nextJ])
            {
                if (have[a[nextI][nextJ]])
                {
                    q.push(make_pair(nextI, nextJ));
                }
                else
                {
                    rooms[a[nextI][nextJ]].push_back(make_pair(nextI, nextJ));
                }
            }
        }
    }
}

int getAns()
{
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans += vis[i][j];

    return ans;
}

int main()
{
    read();
    Fill();
    fout << getAns();
    fout.close();
    return 0;
}