Cod sursa(job #399047)

Utilizator freak93Adrian Budau freak93 Data 19 februarie 2010 19:47:24
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<fstream>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;

const char iname[]="castel.in";
const char oname[]="castel.out";
const int maxn=157;

ifstream f(iname);
ofstream g(oname);

int a[maxn][maxn],i,j,n,m,k,been[maxn][maxn],key[maxn*maxn],x,y,s,dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

vector<pair<int,int> > E[maxn*maxn];

queue<pair<int,int> > Q;

int main()
{
    f>>n>>m>>k;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            f>>a[i][j];
    for(i=1;i<=n;++i)
        a[i][0]=a[i][m+1]=n*m+1;
    for(i=1;i<=m;++i)
        a[0][i]=a[n+1][i]=n*m+1;

    Q.push(make_pair((k-1)/m+1,(k-1)%m+1));
    been[(k-1)/m+1][(k-1)%m+1]=2;
    while(!Q.empty())
    {
        x=Q.front().first;
        y=Q.front().second;
        Q.pop();
        ++s;
        k=(x-1)*m+y;
        key[k]=1;
        for(vector<pair<int,int> >::iterator it=E[k].begin();it!=E[k].end();++it)
            been[it->first][it->second]=2,Q.push(*it);
        E[a[x][y]].clear();
        for(i=0;i<4;++i)
            if(key[a[x+dx[i]][y+dy[i]]]==0)
                if(been[x+dx[i]][y+dy[i]]==0)
                    been[x+dx[i]][y+dy[i]]=1,E[a[x+dx[i]][y+dy[i]]].push_back(make_pair(x+dx[i],y+dy[i]));
                else;
            else
                if(been[x+dx[i]][y+dy[i]]<=1)
                    Q.push(make_pair(x+dx[i],y+dy[i])),been[x+dx[i]][y+dy[i]]=2;
    }

    g<<s<<"\n";

    f.close();
    g.close();

    return 0;
}