Cod sursa(job #2312442)

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

using namespace std;

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

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

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

queue <pair<int, int>> Q;

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

    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 && hasKey[mat[xx][yy]] == true)
                {
                    vis[xx][yy] = true;
                    hasKey[M * (xx - 1) + yy] = true;
                    Q.push(make_pair(xx, yy));
                    sol++;


                }
        }
    }
}

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);

    bool isChange;
    do
    {
        isChange = false;

        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= M; j++)
                if(vis[i][j] == false && hasKey[mat[i][j]] == true)
                    if(vis[i - 1][j] == true || vis[i + 1][j] == true || vis[i][j - 1] == true || vis[i][j + 1] == true)
                    {
                        isChange = true;
                        Lee((i - 1) * M + j);
                    }
    }
    while(isChange == true);

    fout << sol << '\n';

    return 0;
}