Cod sursa(job #198893)

Utilizator hadesgamesTache Alexandru hadesgames Data 15 iulie 2008 19:00:05
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
using namespace std;
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define popf pop_front
int nr,n,m;
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
vector< vector <int> > a,b;
vector<vector<pair<int,int> > > c;
queue<pair<int,int> > q;
int ver[200];
int verif(int x,int y)
{
	if (x<=0||x>n||y<=0||y>m)
		return 0;
	return 1;
}
void pune(int z)
{
	for (vector<pair<int,int> >::iterator it=c[z].begin();it!=c[z].end();it++)
	{
		nr++;
		q.push(*it);
		ver[(it->fs-1)*m+it->ss]=1;
		pune((it->fs-1)*m+it->ss);
	}
	c[z].clear();
}
int main()
{
	int k,x,y;
	ifstream in("castel.in");
	ofstream out("castel.out");
	in>>n>>m>>k;
	a.resize(n+1,vector<int>(m+1,0));
	b.resize(n+1,vector<int>(m+1,0));
	c.resize(n*m+1);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			in>>a[i][j];
		}
	}
	ver[k]=1;
	x=k/m+1;
	y=k%m;
	if (!y)
		y=m;
	b[x][y]=1;
	nr=1;
	q.push(mp(x,y));
	while (!q.empty())
	{
		x=q.front().fs;
		y=q.front().ss;
		q.pop();
		for (int i=0;i<=3;i++)
			if (verif(x+dx[i],y+dy[i])&&!b[x+dx[i]][y+dy[i]])
			{
				if (ver[a[x+dx[i]][y+dy[i]]])
				{
					nr++;
					b[x+dx[i]][y+dy[i]]=1;
					q.push(mp(x+dx[i],y+dy[i]));
					ver[(x+dx[i]-1)*m+y+dy[i]]=1;
					pune((x+dx[i]-1)*m+y+dy[i]);
				}
				else
				{
					b[x+dx[i]][y+dy[i]]=1;
					c[a[x+dx[i]][y+dy[i]]].pb(mp(x+dx[i],y+dy[i]));
				}
			}
			
	}
	out<<nr;
	in.close();
	out.close();
	return 0;
}