Cod sursa(job #906567)

Utilizator ericptsStavarache Petru Eric ericpts Data 6 martie 2013 21:52:50
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <cstdio>
#include <queue>

using namespace std;

#define maxn 160
int mat[maxn][maxn];
bool viz[maxn][maxn];
bool got[maxn*maxn];
int n,m;
int show;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};

struct cell{
    int x,y;
};

inline int toID(int x,int y){
    return (x-1)*m + y;
}
inline int toID(cell c){
    return toID(c.x,c.y);
}

queue<cell> Q;
queue<cell> left[maxn*maxn];
cell toCell(int ID)
{
    int x,y;

    x = (ID / m) + 1;
    y = ID % m;
    if(!y)
        y=m,--x;
    cell C;
    C.x = x;
    C.y = y;
    return C;
}

void lee()
{
    cell C;
    cell P;
    int i,x,y,id;
    while(!Q.empty()){
        C = Q.front();
        Q.pop();
        ++show;
        id = toID(C);
        got[id]=1;
        while(!left[id].empty()){
            P = left[id].front();
            Q.push(P);
            viz[P.x][P.y]=1;
            left[id].pop();
        }
        for(i=0;i<4;++i){
            x = C.x + dx[i];
            y = C.y + dy[i];
            if(x >= 1 && x <= n && y >= 1 && y <= m){
                if(viz[x][y])
                    continue;
                P.x = x;
                P.y = y;
                viz[x][y]=1;
                id = mat[x][y];
                if(got[id]){
                    Q.push(P);
                }else{
                    left[id].push(P);
                }
            }
        }
    }
}

int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);

    int xi,yi,P,i,j;

    scanf("%d %d %d",&n,&m,&P);


    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            scanf("%d",&mat[i][j]);

    cell C = toCell(P);
    got[P]=1;

    viz[C.x][C.y]=1;

    Q.push(C);

    lee();

    printf("%d\n",show);

    return 0;
}