Cod sursa(job #2340640)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 10 februarie 2019 19:27:58
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <deque>
#include <vector>
#define DIM 155
using namespace std;

ifstream fin ("castel.in");
ofstream fout ("castel.out");
int a[DIM][DIM],f[DIM][DIM];
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};
pair <int,int> poz[DIM*DIM];
deque < pair<int,int> > q;
vector <int> L[DIM*DIM];
int n,m,k,i,j,nr,ic,jc,iv,jv,vecin,dir,ii,jj,sol;
int inmat (int i, int j){
    if (i >= 1 && i <= n && j >= 1 && j <= m)
        return 1;
    return 0;
}
int main (){

    fin>>n>>m>>k;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            fin>>a[i][j];
            nr = (i-1)*m+j;
            poz[nr] = make_pair(i,j);
        }

    q.push_back (make_pair(poz[k].first,poz[k].second));
    f[poz[k].first][poz[k].second] = 1;
    while (!q.empty()){

        ic = q.front().first;
        jc = q.front().second;
        q.pop_front();
        for (i=0;i<L[(ic-1)*m+jc].size();i++){ /// camerele care pot fi deschise dupa ce am luat o cheie
            vecin = L[(ic-1)*m+jc][i];
            if (!f[poz[vecin].first][poz[vecin].second]){
                f[poz[vecin].first][poz[vecin].second] = 1;
                q.push_back (make_pair(poz[vecin].first,poz[vecin].second));
            }
        }

        for (dir=0;dir<=3;dir++){
            iv = ic + di[dir];
            jv = jc + dj[dir];
            nr = (iv-1)*m+jv;
            if (inmat(iv,jv) && !f[iv][jv]){
                ii = poz[a[iv][jv]].first, jj = poz[a[iv][jv]].second;
                if (f[ii][jj]){
                    q.push_back (make_pair(iv,jv));
                    f[iv][jv] = 1;
                } else
                    L[a[iv][jv]].push_back ((iv-1)*m+jv);
            }

        }

    }

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            sol += f[i][j];
    fout<<sol;

    return 0;
}