Cod sursa(job #2153796)

Utilizator ioana_marinescuMarinescu Ioana ioana_marinescu Data 6 martie 2018 14:33:20
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
const int MAX_N =  155;
using namespace std;

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

int n, m, k, a[MAX_N][MAX_N], viz[MAX_N][MAX_N], sol, cheie[MAX_N*MAX_N];
int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
vector<int>vecini[MAX_N*MAX_N]; //camere pe care le pot deschide dupa ce iau cheia u
queue<int>q;

int main()
{
    int i, j, x, y;
    fin>>n>>m>>k;
    for(i=0; i<n; i++)
        for(j=0; j<m; j++) {
            fin>>a[i][j];
            a[i][j]--;
        }
    k--;
    q.push(k);
    viz[k/m][k%m]=1;
    while(!q.empty()) {
        sol++;
        int u=q.front();
        cheie[u]=1;
        q.pop();
        for(auto i: vecini[u])
            if(!viz[i/m][i%m]) {
                viz[i/m][i%m]=1;
                q.push(i);
            }
        for(i=0; i<4; i++) {
            x=u/m+dx[i];
            y=u%m+dy[i];
            if(x>=0 && y>=0 && x<n && y<m && !viz[x][y]) {
                if(cheie[a[x][y]]) {
                    q.push(x*m+y);
                    viz[x][y]=1;
                }
                else
                    vecini[a[x][y]].push_back(x*m+y);
            }
        }
    }
    fout<<sol<<'\n';
    return 0;
}