Cod sursa(job #1928917)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 16 martie 2017 21:34:01
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#include <queue>

using namespace std;

struct punct
{
    int x,y;
};

const int vx[4]={-1,0,1,0},vy[4]={0,1,0,-1};

queue<punct> q;
int v[160][160],v1[160][160],vaz[22510],vaz1[22510];
vector<punct> v2[22510];

int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int c=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {scanf("%d",&v[i][j]);v1[i][j]=c;c++;}
    int a=k/m,b=k%m;
    if(b>0) a++;
    else b=m;
    vaz[k]=1;
    q.push({a,b});
    int sol=1;
    while(!q.empty())
    {
        int x=q.front().x,y=q.front().y;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x1=x+vx[i],y1=y+vy[i];
            if(x1<1 or x1>n or y1<1 or y1>m or vaz[v1[x1][y1]]==1) continue;
            if(vaz[v[x1][y1]]==1)
            {
                sol++;
                vaz[v1[x1][y1]]=1;
                q.push({x1,y1});
                for(int j=0;j<v2[v1[x1][y1]].size();j++)
                {
                    int a1=v2[v1[x1][y1]][j].x,b1=v2[v1[x1][y1]][j].y;
                    sol++;
                    vaz[v1[a1][b1]]=1;
                    q.push({a1,b1});
                }
            }
            else {if(vaz1[v1[x1][y1]]==0) v2[v[x1][y1]].push_back({x1,y1});vaz1[v1[x1][y1]]=1;}
        }
    }
    printf("%d",sol);
    return 0;
}