Cod sursa(job #971647)

Utilizator addy01adrian dumitrache addy01 Data 9 iulie 2013 19:43:43
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <queue>
#define MAXN 155
using namespace std;

struct camera
{
    int x,y;
};

queue <camera> Q,Q2;
int viz[MAXN][MAXN];
int a[MAXN][MAXN],n,m,k;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int chei[MAXN*MAXN],camere;
bool parcurs[MAXN][MAXN];

void BFS()
{
    bool ok=1;
    while(ok)
    {
        ok=0;
         Q=Q2;
        while(!Q.empty())
        {

            camera now;
            now=Q.front();
            Q.pop();
            for(int c=0;c<4;c++)
                {
                    camera next;
                    next.x=now.x+dx[c];
                    next.y=now.y+dy[c];

                    if(chei[a[next.x][next.y]]&&viz[next.x][next.y]&&!parcurs[next.x][next.y])
                        {
                            chei[viz[next.x][next.y]]=1;
                            camere++;
                            Q.push(next);
                            Q2.push(next);
                            ok=1;
                            parcurs[next.x][next.y]=1;
                        }
                }

        }


    }
}

int main()
{
    ifstream in("castel.in");
    ofstream out("castel.out");
    int i,j,nr=1;
  camera printesa;
    in>>n>>m>>k;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        in>>a[i][j];
        viz[i][j]=nr++;
        if(viz[i][j]==k)
            printesa.x=i,printesa.y=j,Q.push(printesa),Q2.push(printesa),chei[nr-1]=1;//,camere++;
    }

    for(i=0;i<=n+1;i++)
        a[i][0]=0,a[i][m+1]=0;

    for(j=0;j<=m+1;j++)
        a[0][j]=0,a[n+1][j]=0;

    BFS();

    out<<camere<<"\n";

    return 0;
}