Cod sursa(job #2197680)

Utilizator bogdi1bogdan bancuta bogdi1 Data 22 aprilie 2018 17:52:52
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <cstdio>
#include <queue>
using namespace std;
int lacat[155][155];
struct Camere
{
    int x,y;
} poz[22505];
int f[22505];
queue <int> lin;
queue <int> col;
int viz[155][155];
int dlin[]={-1, 0, 1, 0};
int dcol[]={0, 1, 0, -1};
int m,kk;
bool bfs(int x, int y)
{
    lin.push(x);
    col.push(y);
    int okk=0,ok,i;
    while(!lin.empty()){
        ok=0;
        for(i=0; i<=3; i++){
            if(f[lacat[lin.front()+dlin[i]][col.front()+dcol[i]]]==1 && viz[lin.front()+dlin[i]][col.front()+dcol[i]]==0){
                ok=1;
                f[(lin.front()+dlin[i]-1)*m+col.front()+dcol[i]]=1;
                lin.push(lin.front()+dlin[i]);
                col.push(col.front()+dcol[i]);
                viz[lin.front()+dlin[i]][col.front()+dcol[i]]=1;
            }
        }
        if(viz[lin.front()][col.front()]==1){
            poz[++kk].x=lin.front();
            poz[kk].y=col.front();
            viz[lin.front()][col.front()]=2;
        }
        if(ok==1)
            okk=1;
        lin.pop();
        col.pop();
    }
    return okk;
}
int main()
{   freopen("castel.in", "r",stdin);
    freopen("castel.out", "w", stdout);
    int n,k,i,j,nr;
    scanf("%d%d%d", &n, &m, &k);
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            scanf("%d", &lacat[i][j]);
    f[k]++;
    viz[k/m+1][k-k/m*m+(k%m==0)]=1;
    bfs(k/m+1, k-k/m*m+(k%m==0));
    while(1){
        nr=0;
        for(j=1; j<=kk; j++){
            for(k=0; k<=3; k++)
                if(viz[poz[j].x+dlin[k]][poz[j].y+dcol[k]]==0 && f[lacat[poz[j].x+dlin[k]][poz[j].y+dcol[k]]]==1)
                    nr+=bfs(poz[j].x, poz[j].y);
        }
        if(nr==0)
            break;
    }
    nr=0;
    for(i=1; i<=n*m; i++)
        nr+=f[i];
    printf("%d", nr);
    return 0;
}