Cod sursa(job #1384363)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 11 martie 2015 01:57:00
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 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;
}