Cod sursa(job #2673215)

Utilizator As932Stanciu Andreea As932 Data 16 noiembrie 2020 11:56:31
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int nMax = 155;

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

struct cell{
    int x, y;
};

queue <cell> q;

int n, m, k, ans;
int a[nMax][nMax];
bool vis[nMax][nMax], fq[nMax * nMax];
vector <cell> keys[nMax * nMax];

void read_data(){
    fin >> n >> m >> k;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            fin >> a[i][j];
}

cell keyToCell(int key){
    if(key % m == 0)
        return {key / m, m};
    else
        return {key / m + 1, key % m};
}

int cellToKey(cell a){
    if(a.y < m)
        return ((a.x - 1) * m + a.y);
    else
        return (a.x * m);
}

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

void unlock(int key){
    if(fq[key])
        return;
    fq[key] = 1;

    int len = keys[key].size();
    for(int i = 0; i < len; i++){
        cell c = keys[key][i];
        vis[c.x][c.y] = 1;
        q.push(c);
    }
}

void bfs(){
    cell init = keyToCell(k);
    vis[init.x][init.y] = 1;
    q.push(init);

    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;

        q.pop();

        ans++;

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

            if(ok(l, c) && !vis[l][c]){
                if(fq[a[l][c]])
                    q.push({l, c});
                else
                    keys[a[l][c]].push_back({l, c});
                vis[l][c] = 1;
            }
        }

        unlock(cellToKey({x, y}));
    }

    fout << ans;
}

int main()
{
    read_data();
    bfs();

    return 0;
}