Cod sursa(job #720218)

Utilizator fhandreiAndrei Hareza fhandrei Data 22 martie 2012 14:19:19
Problema Castel Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
//Include
#include <cstdio>
#include <list>
using namespace std;

//Constante
const int MAX_SIZE = 151;
const int P_MAX_SIZE = MAX_SIZE * MAX_SIZE;

//Variabile
int n, m;
int initial, x, y;
int camereVizitate = 1;

int castel[MAX_SIZE][MAX_SIZE];

bool vizitat[P_MAX_SIZE];
bool inList[MAX_SIZE][MAX_SIZE];

list<int> vecini;
list<int>::iterator it, end;

//Main
int main()
{
	freopen("castel.in", "rt", stdin);
	freopen("castel.out", "wt", stdout);
	scanf("%d%d%d", &m, &n, &initial);
	for(int i=1 ; i<=m ; ++i)
		for(int j=1 ; j<=n ; ++j)
			scanf("%d", &castel[i][j]);
	
	vizitat[initial] = true;
	x = initial/n + (initial%n? 1 : 0);
	y = initial%n;   if(!y) y = n;
	
	castel[x][y] = 0;
	
	if(castel[x-1][y])
		vecini.push_back((x-2)*n + y);
	if(castel[x+1][y])
		vecini.push_back(x*n + y);
	if(castel[x][y-1])
		vecini.push_back((x-1)*n + y-1);
	if(castel[x][y+1])
		vecini.push_back((x-1)*n + y+1);
	
	bool key;
	do
	{
		key = false;
		
		end = vecini.end();
		for(it=vecini.begin() ; it!=end ; )
		{
			x = (*it)/n + ((*it)%n? 1 : 0);
			y = (*it)%n;   if(!y) y = n;
			
			if(!vizitat[castel[x][y]])
			{	++it; continue;	}
			
			vizitat[*it] = true;
			++camereVizitate;
			it = vecini.erase(it);
			castel[x][y] = 0;
			
			if(castel[x-1][y] && !inList[x-1][y])
				vecini.push_back((x-2)*n + y), inList[x-1][y] = true;
			if(castel[x+1][y] && !inList[x+1][y])
				vecini.push_back(x*n + y), inList[x+1][y] = true;
			if(castel[x][y-1] && !inList[x][y-1])
				vecini.push_back((x-1)*n + y-1), inList[x][y-1] = true;
			if(castel[x][y+1] && !inList[x][y+1])
				vecini.push_back((x-1)*n + y+1), inList[x][y+1] = true; 
			
			key = true;
		}
		
	} while(key);
	
	printf("%d", camereVizitate);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}