Cod sursa(job #715263)

Utilizator nautilusCohal Alexandru nautilus Data 16 martie 2012 22:12:56
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define NMAX 160

typedef struct pereche
{
 int lin,col;
} pereche;

int n,m,k;
int a[NMAX][NMAX];
bool cheie[NMAX*NMAX];
vector<pereche>listaCamere[NMAX*NMAX];
queue<pereche>q;
int acces;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

void read()
{
 int i,j;
 FILE *fin;
 fin=fopen("castel.in","r");
 fscanf(fin,"%d %d %d",&n,&m,&k);
 for (i=1; i<=n; ++i)
	 for (j=1; j<=m; ++j)
		 fscanf(fin,"%d",&a[i][j]);
 fclose(fin);
}

void transformare(int k, int &lin, int &col)
{
 if (k % m == 0)
	lin = k / m; else
	lin = k / m + 1;
 col = k - (lin - 1) * m;
}

void cheie_noua(int ch)
{
 int i;
 cheie[ch] = 1;
 for (i=0; i<(int)listaCamere[ch].size(); ++i)
	 q.push(listaCamere[ch][i]);
 listaCamere[ch].clear();
}

void solve()
{
 pereche aux,elem;
 int i;

 transformare(k, aux.lin, aux.col);
 cheie[k] = 1; 
 a[aux.lin][aux.col] = 0;
 q.push(aux);

 while (!q.empty())
	{
	 elem = q.front();
	 acces++;
	 cheie_noua((elem.lin - 1) * m + elem.col);
	 for (i=0; i<4; ++i)
		{
		 aux.lin = elem.lin + dx[i];
		 aux.col = elem.col + dy[i];
		 if (cheie[a[aux.lin][aux.col]] == 1)
			{	 
			 q.push(aux);
			 a[aux.lin][aux.col] = 0;
			} 
		 else
			 if (a[aux.lin][aux.col] != 0)
				{
				 listaCamere[a[aux.lin][aux.col]].push_back(aux);
				 a[aux.lin][aux.col] = 0;
				}
		}
	 q.pop();
	}
}

void write()
{
 FILE *fout;
 fout=fopen("castel.out","w");
 fprintf(fout,"%d\n",acces);
 fclose(fout);
}

int main()
{
 read();
 solve();
 write();
 return 0;
}