Cod sursa(job #2312463)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 4 ianuarie 2019 21:26:38
Problema Castel Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");

int N, M, sol, mat[155][155];
bool vis[155][155], hasKey[22505];

vector <int> keysUnvisited[22505];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

queue <pair<int, int>> Q;

void Lee(int K)
{
    if(K == -1)
        return ;

    int xi = (K - 1) / M + 1, yi = (K - 1) % M + 1;

    if(vis[xi][yi] == true)
        return ;

    vis[xi][yi] = true;
    hasKey[K] = true;
    Q.push(make_pair(xi, yi));
    sol++;

    while(!Q.empty())
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();

        for(int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];

            if(1 <= xx && xx <= N && 1 <= yy && yy <= M)
                if(vis[xx][yy] == false)
                {
                    if(hasKey[mat[xx][yy]] == true)
                    {
                        vis[xx][yy] = true;
                        hasKey[M * (xx - 1) + yy] = true;
                        Q.push(make_pair(xx, yy));
                        sol++;

                        for(unsigned int i = 0; i < keysUnvisited[M * (xx - 1) + yy].size(); i++)
                        {
                            int leeK = keysUnvisited[M * (xx - 1) + yy][i];
                            keysUnvisited[M * (xx - 1) + yy][i] = -1;

                            Lee(leeK);
                        }
                    }
                    else
                        keysUnvisited[mat[xx][yy]].push_back((xx - 1) * M + yy);
                }
        }
    }
}

int main()
{
    int K;
    fin >> N >> M >> K;

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            fin >> mat[i][j];

    Lee(K);

    fout << sol << '\n';

    return 0;
}