Cod sursa(job #609620)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 22 august 2011 14:53:01
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<fstream>
#include<iostream>
#include<queue>
using namespace std;
int n,m,K,xp,yp;
struct Room{short x,y;};
Room a[155][155];
bool key[155][155];
int vizitat[155][155];
int nrsol[1000000];
int sol;

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

void Citire()
{
	int i,j,lim,x,pas;
	Room aux;
	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;
		j++;
		if(j>m)
		{
			i++;
			j=1;
		}
	}
	fin.close();
}

void BFS()
{
	int k,pas;
	Room aux,aux2,cheie;
	queue <Room> Q;
	
	aux.x=xp;
	aux.y=yp;
	Q.push(aux);
	vizitat[xp][yp]=true;
	sol=1;
	nrsol[1]=sol;
	pas=2;
	while(!Q.empty())
	{
		aux=Q.front();
		Q.pop();
		key[aux.x][aux.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
			{
				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
				{
					sol++;
					Q.push(aux2);
					vizitat[aux2.x][aux2.y]=pas;
					nrsol[pas]=sol;
					pas++;
				}
				else
					if(vizitat[aux2.x][aux2.y] && sol!=nrsol[vizitat[aux2.x][aux2.y]])
					{
						Q.push(aux2);
						vizitat[aux2.x][aux2.y]=pas;
						nrsol[pas]=sol;
						pas++;
					}
			}
		}
	}
}

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

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