比赛 NOIP2008集训模拟2 评测结果 AAWWTWWTTTTTTTTAATTT
题目名称 奥术能量环流 最终得分 20
用户昵称 zqzas 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2008-11-11 11:22:38
显示代码纯文本
#include <iostream>

#define MAXN 111

using namespace std;

const int Dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,m,now,flag_first,beg_x,beg_y,c,ans,color[MAXN][MAXN],visit[MAXN][MAXN],dir[MAXN][MAXN][8];

bool dfs(int x,int y)
{
	if (x==beg_x && y==beg_y)
	{
		if (flag_first)
			return true;
		else
			flag_first=1;
		visit[x][y]=0;
	}
	int d,a,b;
	bool flag=false;
	for (d=0;d<4;d++)
	{
		if (dir[x][y][d])
		{
			a=x+Dir[d][0];
			b=y+Dir[d][1];
			if (a>=1 && a<=n && b>=1 && b<=m)
			{
				if (visit[a][b]!=c)
				{
					visit[a][b]=c;
					if (dfs(a,b))
					{
						flag=true;
						color[a][b]=c;
						now++;
					}
					visit[a][b]=0;
				}
			}
		}
	}
	return flag;
}

void run()
{
	int i,j,p=0;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			if (color[i][j]==0)
			{
				p++;
				color[i][j]=c=p;
				beg_x=i;
				beg_y=j;
				now=1;
				flag_first=0;
				dfs(i,j);
				if (now!=1)
					ans++;
			}
		}
}

void ini()
{
	int i,j,a;
	cin>>n>>m;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			cin>>a;
			dir[i][j][0]=( (a & (1<<3) )==1<<3);
			dir[i][j][1]=( (a & (1<<2) )==1<<2);
			dir[i][j][2]=( (a & (1<<1) )==1<<1);
			dir[i][j][3]=( (a & (1) )==1);
		}
}

int main()
{
	freopen("arcane.in","r",stdin);
	freopen("arcane.out","w",stdout);
	ini();
	run();
	cout<<ans;
	return 0;
}