Cod sursa(job #1066991)

Utilizator dariusdariusMarian Darius dariusdarius Data 25 decembrie 2013 22:45:18
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int a[155][155];
int key[150*150+5];
bool viz[155][155];
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
vector< pair<int,int> > List,NewList;
int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);
    int N,M,start;
    scanf("%d%d%d",&N,&M,&start);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            scanf("%d",&a[i][j]);
    int x,y,xn,yn;
    x=(start-1)/M+1;
    y=start-(x-1)*M;
    key[start]=1;viz[x][y]=true;
    List.push_back(make_pair(x,y));
    bool flag;
    do
    {
        flag=true;
        NewList.clear();
        for(vector< pair<int,int> >::iterator it=List.begin();it!=List.end();it++)
        {
            x=it->first;y=it->second;bool second_flag=true;
            for(int d=0;d<4;d++)
            {
                xn=x+dx[d];yn=y+dy[d];
                if(1<=xn && xn<=N && 1<=yn && yn<=M && !viz[xn][yn] && key[a[xn][yn]])
                {
                    NewList.push_back(make_pair(xn,yn));
                    key[(xn-1)*M+yn]=1;
                    viz[xn][yn]=true;
                    flag=false;
                }
                if(1<=xn && xn<=N && 1<=yn && yn<=M && !viz[xn][yn])
                    second_flag=false;
            }
            if(!second_flag)
                NewList.push_back(*it);
        }
        List=NewList;
    }while(!flag);
    int Ans=0;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            Ans+=viz[i][j];
    printf("%d\n",Ans);
    return 0;
}