Cod sursa(job #1105825)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 12 februarie 2014 09:53:17
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");
int M,N;
int K;
queue <int> Line;
queue <int> Col;
queue <int> Place[155];
int Matrix[155][155];
bool Use[155*155];
bool InQ[155][155];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int Result;
void Read()
{
    int i,j;
    f>>M>>N>>K;
    for(i=1;i<=M;i++)
        for(j=1;j<=N;j++)
            f>>Matrix[i][j];
}
inline bool Valid(int x,int y)
{
    return x>0 && x<=M && y>0 && y<=N;
}
void Browse_Q(int room)
{
    int i;
    while(!Place[room].empty())
    {
        int aux=Place[room].front();
        Place[room].pop();
        Use[aux]=1;
        Line.push(aux/N+1);
        if(aux%N!=0)
            Col.push(aux%N);
        else
            Col.push(N);
        /*for(i=0;i<4;i++)
            if((Valid((x+dx[i]-1)*N+y+dy[i]))==1 && Use[(x+dx[i]-1)*N+y+dy[i]]==0 && InQ[Matrix[x+dx[i]][y+dy[i]]][(x+dx[i]-1)*N+y+dy[i]]==0)
            {
                InQ[Matrix[x+dx[i]][y+dy[i]]][(x+dx[i]-1)*N+y+dy[i]]=1;
                Place[Matrix[x+dx[i]][y+dy[i]]].push((x+dx[i]-1)*N+y+dy[i]);*/
            //}
    }
}
void Solve()
{
    int i;
    Line.push(K/N+1);
    if(K%N!=0)
        Col.push(K%N);
    else
        Col.push(N);
    Use[K]=1;
    while(!Line.empty())
    {
        int x=Line.front();
        int y=Col.front();
        Line.pop();
        Col.pop();
        Use[(x-1)*N+y]=1;
        if(Valid(x,y)==0)
            continue;
        for(i=0;i<4;i++)
            if(Valid(x+dx[i],y+dy[i])==1 && Use[(x+dx[i]-1)*N+y+dy[i]]==0 && InQ[Matrix[x+dx[i]][y+dy[i]]][(x+dx[i]-1)*N+y+dy[i]]==0)
            {
                InQ[Matrix[x+dx[i]][y+dy[i]]][(x+dx[i]-1)*N+y+dy[i]]=1;
                Place[Matrix[x+dx[i]][y+dy[i]]].push((x+dx[i]-1)*N+y+dy[i]);
                if(Use[Matrix[x+dx[i]][y+dy[i]]]==1)
                    Browse_Q(Matrix[x+dx[i]][y+dy[i]]);
            }
        Browse_Q((x-1)*N+y);
    }
}
int main()
{
    Read();
    Solve();
    for(int i=1;i<=M*N;i++)
        if(Use[i]==1)
            Result++;
    g<<Result<<"\n";
    return 0;
}