Cod sursa(job #1653174)

Utilizator delia_99Delia Draghici delia_99 Data 15 martie 2016 19:32:02
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <queue>
#include <vector>
#define NMAX 150

using namespace std;

int n,m,k,M[NMAX+5][NMAX+5],sol,i,j;
queue <int>q;
bool ok[NMAX*NMAX+5],room[NMAX+5][NMAX+5];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector <int> v[NMAX*NMAX+5];

void coord(int &i,int &j)
{
    if(k%m==0)
    {
        i=k/m;
        j=m;
    }
    else
    {
        i=k/m+1;
        j=k%m;
    }
}

bool limite(int x,int y)
{
    if(x>0 && y>0 && x<=n && y<=m)
        return true;
    return false;
}

void lee()
{
    int x,y,xx,yy,val,cod;
    while(!q.empty())
    {
        val=q.front();
        x=val/1000;
        val-=(val/1000)*1000;
        y=val;
        q.pop();
        if(room[x][y])
            continue;
        ++sol;
        cod=(x-1)*m+y;
        ok[cod]=true;
        room[x][y]=true;
        for(int k=0;k<4;++k)
        {
            xx=x+dx[k];
            yy=y+dy[k];
            if(limite(xx,yy) && !room[xx][yy])
            {
                if(ok[M[xx][yy]])
                    q.push(xx*1000+yy);
                else v[M[xx][yy]].push_back(xx*1000+yy);
            }
        }
        int s=v[cod].size();
            for(i=0;i<s;++i)
                q.push(v[cod][i]);
    }
}

int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            scanf("%d",&M[i][j]);
    coord(i,j);
    q.push(i*1000+j);
    lee();
    printf("%d\n",sol);
    return 0;
}