Cod sursa(job #601389)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 6 iulie 2011 11:47:45
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define NMax 155

using namespace std;

int N, M, Start, ReqKey[NMax][NMax], RoomX[NMax*NMax], RoomY[NMax*NMax], RoomN[NMax][NMax], XV[4]={-1, 0, 1, 0}, YV[4]={0, 1, 0, -1};
bool Key[NMax*NMax], Viz[NMax][NMax], InQ[NMax*NMax];
queue <int> Q;
vector <int> KeyOpen[NMax*NMax];

void Read ()
{
    ifstream fin ("castel.in");
    int x=0;
    fin >> N >> M >> Start;
    for (int i=1; i<=N; ++i)
    {
        for (int j=1; j<=M; ++j)
        {
            fin >> ReqKey[i][j];
            ++x;
            RoomN[i][j]=x;
            RoomX[x]=i;
            RoomY[x]=j;
            KeyOpen[ReqKey[i][j]].push_back (x);
        }
    }
    fin.close ();
}

void Print ()
{
    ofstream fout ("castel.out");
    int S=0;
    for (int i=1; i<=N; ++i)
    {
        for (int j=1; j<=M; ++j)
        {
            if (Viz[i][j])
            {
                S++;
            }
        }
    }
    fout << S << "\n";
    fout.close ();
}

bool Valid (int X, int Y)
{
    if (X>0 and X<=N and Y>0 and Y<=M)
    {
        return true;
    }
    return false;
}

bool CheckRooms ()
{
    int NewX, NewY;
    for (int X=1; X<=N; ++X)
    {
        for (int Y=1; Y<=M; ++Y)
        {
            if (!Viz[X][Y] and Key[ReqKey[X][Y]])
            {
                for (int d=0; d<4; ++d)
                {
                    NewX=X+XV[d];
                    NewY=Y+YV[d];
                    if (Viz[NewX][NewY])
                    {
                        Start=RoomN[X][Y];
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

void Lee ()
{
    int X, Y, Room, NewX, NewY;
    Q.push (Start);
    while (!Q.empty ())
    {
        Room=Q.front ();
        Q.pop ();
        InQ[Room]=false;
        X=RoomX[Room];
        Y=RoomY[Room];
        Key[Room]=true;
        Viz[X][Y]=true;
        for (int d=0; d<4; ++d)
        {
            NewX=X+XV[d];
            NewY=Y+YV[d];
            if (Valid (NewX, NewY) and Key[ReqKey[NewX][NewY]] and !Viz[NewX][NewY])
            {
                Q.push (RoomN[NewX][NewY]);
                InQ[RoomN[NewX][NewY]]=true;
            }
        }
        for (int i=0; i<KeyOpen[Room].size (); ++i)
        {
            X=RoomX[KeyOpen[Room][i]];
            Y=RoomY[KeyOpen[Room][i]];
            if (!Viz[X][Y])
            {
                for (int d=0; d<4; ++d)
                {
                    NewX=X+XV[d];
                    NewY=Y+YV[d];
                    if (Valid (NewX, NewY) and Viz[NewX][NewY])
                    {
                        if (InQ[KeyOpen[Room][i]]==false)
                        {
                            Q.push (KeyOpen[Room][i]);
                            InQ[KeyOpen[Room][i]]=true;
                        }
                        break;
                    }
                }
            }
        }
    }
}

int main()
{
    Read ();
    do
    {
        Lee ();
    }
    while (CheckRooms ());
    Print ();
    return 0;
}