Cod sursa(job #715682)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 17 martie 2012 16:42:13
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
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;

vector<vector<int> > camera(155*155, 50);
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;
		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;
	
}