Cod sursa(job #1164787)

Utilizator HashiraGrigore Vlad Hashira Data 2 aprilie 2014 12:15:19
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <vector>
#include <queue>

#define inside(x,y) (x>=1 && x<=n && y>=1 && y<=m)
#define room(x,y) ((x-1)*m+y)

using namespace std;

int n,m,k;

int a[155][155];
int key[155][155];
bool viz[155][155];

int dx[]={-1, 0, 1, 0},
	dy[]={ 0, 1, 0,-1};

struct POINT
{
	int x,y;
};

queue<POINT> q;
vector<POINT> v[23000];

inline void roomn(int x,int *i,int *j)
{
	*i=x/m+1;
	*j=x%m;
	if(*j==0)
	{
		(*i)--;
		*j=m;
	}
}

void solve()
{
	POINT tata,fiu;
	roomn(k,&tata.x,&tata.y);
	q.push(tata);
	viz[tata.x][tata.y]=true;

	vector<POINT>::iterator it;

	int l;
	int num=0;
	int p;

	int x,y;

	while(!q.empty())
	{
		tata=q.front();
		num++;

		p=room(tata.x,tata.y);

		for(it=v[p].begin();it!=v[p].end();++it)
		{
			if(!viz[it->x][it->y])
			{
				q.push(*it);
				viz[it->x][it->y]=true;
			}
		}

		for(l=0;l<4;++l)
		{
			fiu.x=tata.x+dx[l];
			fiu.y=tata.y+dy[l];

			if(!inside(fiu.x,fiu.y))
				continue;

			if(viz[fiu.x][fiu.y])
				continue;

			p=a[fiu.x][fiu.y];
			roomn(p,&x,&y);

			if(viz[x][y])
			{
				viz[fiu.x][fiu.y]=true;
				q.push(fiu);
			}
			else
				v[p].push_back(fiu);
		}

		q.pop();
	}

	printf("%d",num);
}

int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);

    scanf("%d%d%d",&n,&m,&k);

	int i,j;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			scanf("%d",&a[i][j]);

	solve();

    return 0;
}