Cod sursa(job #715590)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 17 martie 2012 15:00:25
Problema Castel Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
char cp[155*155],cheie[155*155];
short 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;
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]=1;
		cheie[(l-1)*m+c]=1;
		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]][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;
	
}