Cod sursa(job #667645)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 23 ianuarie 2012 16:09:53
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
using namespace std;
struct coada {
	unsigned short x,y;
};
coada c[2050501];
vector <coada> cheier[25501];
unsigned short a[155][155];
bitset <155> d[155];
bitset <155> cc[155];
bitset <22501> v;
bitset <155>  adug[155];
int main ()
{
	int n,m,k,st,dr,nr,j,i,cheien,cheienn,cg;
	coada aa,b;
	int dx[]={0,-1,0,1,0};
	int dy[]={0,0,1,0,-1};
	ifstream f("castel.in");
	ofstream g("castel.out");
	f>>n>>m>>k;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			f>>a[i][j];
	f.close();
	if(k%m==0) {
		c[1].x=k/m;
		c[1].y=m;
	}
	else {
		c[1].x=k/m+1;
		c[1].y=k%m;
	}
	st=1;
	dr=1;
	d[c[1].x][c[1].y]=1;
	cc[c[1].x][c[1].y]=1;
	v[a[c[1].x][c[1].y]]=1;
	nr=1;
	while(st<=dr) {
		aa=c[st];
		st++;
		cc[aa.x][aa.y]=0;
		cheien=(aa.x-1)*m+aa.y;
		v[cheien]=1;
		for(j=0;j<cheier[cheien].size();j++) {
			if(d[cheier[cheien][j].x][cheier[cheien][j].y]==0)
				nr++;
			d[cheier[cheien][j].x][cheier[cheien][j].y]=1;
			cg=(cheier[cheien][j].x-1)*m+cheier[cheien][j].y;
			v[cg]=1;
			if(cc[cheier[cheien][j].x][cheier[cheien][j].y]==0) {
				dr++;
				c[dr]=cheier[cheien][j];
			}
			cheier[cheien].erase(cheier[cheien].begin()+j);
		}
		for(i=1;i<=4;i++) {
			b.x=aa.x+dx[i];
			b.y=aa.y+dy[i];
			if(a[b.x][b.y])	{
				cheienn=a[b.x][b.y];
				if((d[b.x][b.y]==0)&&(v[cheienn]==1)) {
					d[b.x][b.y]=1;
					cc[b.x][b.y]=1;
					dr++;
					c[dr]=b;
					nr++;
					cheien=(b.x-1)*m+b.y;
					v[cheien]=1;
					for(j=0;j<cheier[cheien].size();j++) {
						if(d[cheier[cheien][j].x][cheier[cheien][j].y]==0)
							nr++;
						d[cheier[cheien][j].x][cheier[cheien][j].y]=1;
						cg=(cheier[cheien][j].x-1)*m+cheier[cheien][j].y;
						v[cg]=1;
						if(cc[cheier[cheien][j].x][cheier[cheien][j].y]==0) {
							dr++;
							c[dr]=cheier[cheien][j];
						}
						cheier[cheien].erase(cheier[cheien].begin()+j);
					}
				}
				else if((d[b.x][b.y]==0)&&(v[cheienn]==0)&&(adug[b.x][b.y]==0)) {
					cheier[cheienn].push_back(b);
					adug[b.x][b.y]=1;
				}
			}
		}
	}
	g<<nr;
	g.close();
	return 0;
}