Cod sursa(job #2312468)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 4 ianuarie 2019 21:43:32
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#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 < pair<int, int> > Q;

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

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

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

    bool canChange = true;

    while(canChange == true)
    {
        canChange = false;

        for(unsigned int i = 0; i < Q.size(); i++)
        {
            int x = Q[i].first;
            int y = Q[i].second;

            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_back(make_pair(xx, yy));
                            sol++;
                            canChange = true;
                        }
                    }
            }
        }
    }
}

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