Pagini recente » Cod sursa (job #3165022) | Cod sursa (job #3153901) | Cod sursa (job #2205394) | Cod sursa (job #2507691) | Cod sursa (job #601389)
Cod sursa(job #601389)
#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;
}