Cod sursa(job #1138750)

Utilizator thewildnathNathan Wildenberg thewildnath Data 10 martie 2014 15:55:39
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;

#define NMAX 152
#define MAXI NMAX*NMAX

struct punct
{
    int x,y;
}a,aux;

queue<punct>q;
vector<punct>list[MAXI];

int n,m,k,sol;
bool f[MAXI];
int v[NMAX][NMAX],viz[NMAX][NMAX];
int dx[]={0,-1,0,1,0},dy[]={0,0,1,0,-1};


inline bool bun(int x,int y)
{
    if(viz[x][y])
        return 0;
    int i,x1,y1;

    for(i=1;i<=4;++i)
    {
        x1=x+dx[i];
        y1=y+dy[i];
        if(viz[x1][y1]==1)
            return 1;
    }
    return 0;
}


void bfs()
{
    int i,nr;

    a.x=(k-1)/m+1;
    a.y=(k-1)%m+1;

    viz[a.x][a.y]=1;
    q.push(a);

    while(!q.empty())
    {
        a=q.front();
        q.pop();

        nr=(a.x-1)*m+a.y;

        if(!f[nr])
        {
            f[nr]=1;
            for(i=0;i<list[nr].size();++i)
            {
                v[list[nr][i].x][list[nr][i].y]=0;
                if(bun(list[nr][i].x,list[nr][i].y))
                {
                    aux=list[nr][i];
                    viz[aux.x][aux.y]=1;
                    q.push(aux);
                }
            }
        }

        for(i=1;i<=4;++i)
        {
            aux.x=a.x+dx[i];
            aux.y=a.y+dy[i];

            if(f[v[aux.x][aux.y]]&&!viz[aux.x][aux.y])
            {
                viz[aux.x][aux.y]=1;
                q.push(aux);
            }
        }
    }
}


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

    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)
        {
            scanf("%d",&v[i][j]);
            aux.x=i;aux.y=j;
            list[v[i][j]].push_back(aux);
        }
    }
    for(i=1;i<=n;++i)
        viz[i][0]=viz[i][m+1]=MAXI-1;
    for(j=1;j<=m;++j)
        viz[0][j]=viz[n+1][j]=MAXI-1;

    f[0]=1;

    bfs();

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(viz[i][j])
                ++sol;

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

    return 0;
}