Cod sursa(job #715686)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 17 martie 2012 16:47:21
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
bool cp[155*155],cheie[155*155];
int a[155][155],camera[155*155][50];
int lin[]={12,-1,0,1,0};
int col[]={12,0,1,0,-1};
queue<int> qlin,qcol;
struct pereche
{
	int lin,col;
}
vector<pereche>camera[155*155];
int n,m,nr;
void key(int nr, int &l ,int &c)
{
	if (nr%m==0)
	{
		l=nr/m;
		c=m;
	}
	else
	{
		l=nr/m+1;
		c=nr%m;
	}
}
int main(void)
{
	int i,j;
	int k;
	fstream f,g;
	f.open("castel.in",ios::in);
	g.open("castel.out",ios::out);
	f>>n>>m>>k;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			f>>a[i][j];
	int l,c;
	key(k,l,c);
	qlin.push(l);
	qcol.push(c);
	while (!qlin.empty())
	{
		l=qlin.front();
		c=qcol.front();
		qlin.pop();
		qcol.pop();
		cp[(l-1)*m+c]=true;
		cheie[(l-1)*m+c]=true;
		int ch=(l-1)*m+c;
		
		
		for (i=0; i<(int)listaCamere[ch].size(); ++i)
			{
				qlin.push(camera[ch][i].lin);
				qcol.push(camera[ch][i].col);
			}
		listaCamere[ch].clear();
/*		for (i=camera[(l-1)*m+c][0];i>0;i--)
		{
			int l1,c1;
			key(camera[(l-1)*m+c][i],l1,c1);
			qlin.push(l1);
			qcol.push(c1);
		}
		*/
		//if (i==0)
		//camera[(l-1)*m+c][0]=0;
/*		for (i=1;i<=4;i++)
		{
				int l1,c1;
				l1=l+lin[i];
				c1=c+col[i];
				if (l1>=1 && l1<=n && c1>=1 && c1<=m){
				if (cheie[a[l1][c1]]==1 )
				{
					if (cp[(l1-1)*m+c1]==0)
					{qlin.push(l1);
					qcol.push(c1);
					}
				}
				else
				{
					camera[a[l1][c1]].lin.push_back(l1);
					camera[a[l1][c1]].col.push_back(c1);
					//camera[a[l1][c1]][0]++;
					//camera[ a[l1][c1] ][camera[a[l1][c1]][0]]=(l1-1)*m+c1;
				}}
		}
	}
	
	for (i=1;i<=n*m;i++)
		if (cp[i])
			nr++;
	g<<nr;
	
}
*/
#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;
}