Cod sursa(job #1167146)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 4 aprilie 2014 14:34:31
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int a[160][160];
bool f[160][160];
bool keys[30000];
bool waiting[160][160];
int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};

struct poz
{
	int x, y;
};
queue <poz> q;
vector <poz> wait[30000];

int main()
{
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);
	int n, m, start;
	scanf("%d%d%d", &n, &m, &start);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d", &a[i][j]);
	poz t;
	t.x=(start-1)/m;
	t.y=(start-1)%m;
	q.push(t);
	f[t.x][t.y]=1;
	keys[start]=1;
	while(!q.empty())
	{
		t=q.front();
		for(int k=0;k<4;k++)
		{
			int i=t.x+dx[k];
			int j=t.y+dy[k];

			if(i>=0 && j>=0 && i<n && j<m)
			if(!f[i][j])
			{
				poz t2;
				t2.x=i;t2.y=j;
				if(keys[a[i][j]]==1)
				{
					f[i][j]=1;
					q.push(t2);
					int found=i*m+j+1;
					for(int l=0;l<wait[found].size();l++)
					{
						q.push(wait[found][l]);
						f[wait[found][l].x][wait[found][l].y]=1;
						keys[wait[found][l].x*m+wait[found][l].y+1]=1;
					}
					keys[found]=1;
				}
				else if(!waiting[i][j])
				{
					wait[a[i][j]].push_back(t2);
					waiting[i][j]=1;
				}
			}
		}
		q.pop();
	}
	int nr=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(f[i][j])
				nr++;
	printf("%d", nr);
    return 0;
}