Cod sursa(job #609630)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 22 august 2011 15:24:18
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<fstream>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
int n,m,K,xp,yp;
struct Room{short x,y;};
Room a[155][155];
bool key[155][155],vizitat[155][155],acces[155][155];
int sol;
vector <Room> need[155][155];

short dx[]={0,1,0,-1};
short dy[]={1,0,-1,0};

void Citire()
{
	int i,j,lim,x,pas;
	Room aux,aux2;
	ifstream fin("castel.in");
	fin>>n>>m>>K;
	
	xp=K/m+1;
	yp=K%m;
	if(yp==0)
	{
		xp--;
		yp=m;
	}
	key[xp][yp]=true;
	
	lim=n*m;
	i=j=1;
	for(pas=1;pas<=lim;pas++)
	{
		fin>>x;
		aux.x=x/m+1;
		aux.y=x%m;
		if(aux.y==0)
		{
			aux.x--;
			aux.y=m;
		}
		a[i][j]=aux;
		aux2.x=i;
		aux2.y=j;
		need[aux.x][aux.y].push_back(aux2);
		j++;
		if(j>m)
		{
			i++;
			j=1;
		}
	}
	fin.close();
}

void DFS()
{
	int k;
	Room aux,aux2,cheie;
	stack <Room> S;
	vector <Room>::iterator it;
	
	aux.x=xp;
	aux.y=yp;
	S.push(aux);
	vizitat[xp][yp]=true;
	acces[xp][yp]=true;
	
	while(!S.empty())
	{
		aux=S.top();
		S.pop();
		key[aux.x][aux.y]=true;
		sol++;
		
		for(it=need[aux.x][aux.y].begin();it!=need[aux.x][aux.y].end();it++)
		{
			aux2=*it;
			if(!vizitat[aux2.x][aux2.y] && acces[aux2.x][aux2.y]) //am avut candva acces la camera si acum am si cheia
			{
				S.push(aux2);
				vizitat[aux2.x][aux2.y]=true;
			}
		}
		
		for(k=0;k<4;k++)
		{
			aux2.x=aux.x+dx[k];
			aux2.y=aux.y+dy[k];
			if(0<aux2.x && aux2.x<=n && 0<aux2.y && aux2.y<=m) //exista camera
			{
				acces[aux2.x][aux2.y]=true;
				cheie=a[aux2.x][aux2.y];
				if(!vizitat[aux2.x][aux2.y] && key[cheie.x][cheie.y]) //nu a mai fost vizitata si am cheia
				{
					S.push(aux2);
					vizitat[aux2.x][aux2.y]=true;
				}
			}
		}
	}
}

void Afisare()
{
	ofstream fout("castel.out");
	fout<<sol<<"\n";
	fout.close();
}

int main()
{
	Citire();
	DFS();
	Afisare();
	return 0;
}