Cod sursa(job #616269)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 12 octombrie 2011 00:41:47
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.97 kb
#include <fstream>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n, m, camerai; //  n = nr lnii, m = nr coloane, camera = nr camerei initiale
short a[152][152], sol; //  a[i][j] = ce cheie am nevoie ca sa deschid a[i][j]
short A[] = {1, 0, -1, 0}; // vector de deplasare...
short B[] = {0, 1, 0, -1};
short viz[152][152]; // viz[i][j] = 0 daca nu am vizitat; 1 daca e pe lista de asteptare; 2 daca e vizitata
struct Cheie
{
	bool cheie; 
	vector <short> camere;
};
Cheie key[22510];
// cheie = true daca am cheia i;
// camere = retine camerele la care am avut acces candva, pentru ca apoi sa le bag in stiva cand capat o cheie;


bool chei[22510]; //  chei [i] = true daca am cheie obtinuta pentru camera i;
struct Room
{
	short x, y;
};
Room st[22510]; //  am declarat stiva

void Citire()
{
	freopen ("castel.in", "r", stdin);
	scanf("%d %d %d", &n, &m, &camerai);
	int i, j;
	for (i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			scanf("%hd", &a[i][j]);
}

void Afisare()
{
	int i, j;
	cout<<n<<" "<<m<<" "<<camerai<<"\n";
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
			cout<<a[i][j]<<" ";
		cout<<"\n";
	}
}

inline short ToCamera (short x, short y)
{
	return m*(x-1) + y;
}

inline void ToCoord (short c, short &x, short &y)
{
	y = c%m;
	if (y == 0)
		y = m;
	c -= y;
	x = c/m + 1;
}

void Rezolvare()
{
	short vf, x, y, x0, y0, i, j, k, camera, camera1, N, ok;
	ToCoord(camerai , x0, y0);
	
	viz[x0][y0] = 2;
	sol++;
	key[camerai].cheie = true;
	
	cout<<camerai<<"  ";
	
	vf = 1;
	st[vf].x = x0;
	st[vf].y = y0;
	while (vf > 0) // cat timp stiva nu este goala
	{
		i = st[vf].x;
		j = st[vf].y;
		camera = ToCamera(i, j);
		vf--;
		sol++;
		N = key[camera].camere.size();
		//sol += N; // aici cresc solutia pentru fiecare camera la care am avut acces candva si pe care acum le vizitez si la bag si in stiva
		if (N)
		{
			for(int k1 = 0; k1<N; k1++)
			{
				camera1 = key[camera].camere[k1];
				ToCoord(camera1, x0, y0);
				key[camera1].cheie = true;
				vf++;			// pun in stiva...
				st[vf].x = x0;
				st[vf].y = y0;
				viz[x0][y0] = 2; // marchez ca vizitat
			}
			key[camera].camere.clear(); // il distrug
		}
		
		ok = 1;
		for(k=0; k<4; k++)
		{
			x = i + A[k];
			y = j + B[k];
			if (viz[x][y] == 0 && key[a[x][y]].cheie == true) // daca nu am intrat in camera x, y dar am cheie, atunci intru si cresc solutia si bag in stiva si capat o noua cheie
			{
				ok = 0;
				viz[x][y] = 2; // intru
				//sol++;			// cresc solutia
				vf++;			// bag in stiva
				st[vf].x = x;
				st[vf].y = y;
				camera = ToCamera(x, y);
				key[camera].cheie = true; // capat noua cheie
				// aici trebuie sa 	adaug toate camerele la care am avut acces candva si care se pot deschide cu noua cheie
				N = key[camera].camere.size();
				//sol += N; // aici cresc solutia pentru fiecare camera la care am avut acces candva si pe care acum le vizitez si la bag si in stiva
				if (N)
				{
					for(int k1 = 0; k1<N; k1++)
					{
						camera1 = key[camera].camere[k1];
						ToCoord(camera1, x0, y0);
						key[camera1].cheie = true;
						vf++;			// pun in stiva...
						st[vf].x = x0;
						st[vf].y = y0;
						viz[x0][y0] = 2; // marchez ca vizitat
					}
					key[camera].camere.clear(); // il distrug
				}
			}
			else
				if(viz[x][y] == 0 && key[a[x][y]].cheie == false) //  daca nu am intrat in camera x dar nu am cheie atunci o pun pe lista de asteptare
				{
					ok = 0;
					key[a[x][y]].camere.push_back(ToCamera(x, y)); // pun camera x, y pe lista de asteptare
					viz[x][y] = 1;					
				}
		}
		//if (ok == 1)
		//	vf--;
	}
}

void Afis()
{
	int i, j;
	cout<<"\n\n";
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
			cout<<viz[i][j]<<" ";
		cout<<"\n";
	}
}

void Scriere()
{
	freopen ("castel.out", "w", stdout);
	printf ("%d\n", sol-1);	
}

int main()
{
	Citire();
	//Afisare();
	Rezolvare();
	//Afis();
	Scriere();
	return 0;
}