首页 > 搜索 > BFS搜索 > HDU 3375-XieGang and FanXieGang-BFS-[解题报告]HOJ
2014
03-16

HDU 3375-XieGang and FanXieGang-BFS-[解题报告]HOJ

XieGang and FanXieGang

问题描述 :

  As we know, ‘/’ in chinese is “Xie Gang”, and ‘\’ is “Fan Xie Gang”, we can use them to build a beautiful labyrinth, for example :
String Problem

here ‘/’ and ‘\’ in the labyrinth means walls, the wall which can’t separate two rooms we call it “inner wall”, for example, in he figure below, there are three “inner wall”s.
String Problem

输入:

  There are no more than 20000 cases. each case contains two integers n and m(n,m<=500), the width and the height of the labyrinth, The next m lines represent the labyrinth itself, and contain n characters each, all these characters will be "/" or "\".

输出:

  There are no more than 20000 cases. each case contains two integers n and m(n,m<=500), the width and the height of the labyrinth, The next m lines represent the labyrinth itself, and contain n characters each, all these characters will be "/" or "\".

样例输入:

3 3
\/\
/\\
/\/
4 4
////
\\\\
////
\\\\

样例输出:

2
0

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define max 510
int mo[4][2]={ {-1,0}, {0,1}, {1,0}, {0,-1} };
struct node{
	int ge[4];
	int vis[4];
	int fuhao;
}map[max][max];
struct data{           //每个1/4区域 map[x][y]的第g块
	int x,y,g;  
}d[max][max][4]; 
int m,n,color,white;
void bfs(int x,int y,int r)      //染色
{
	queue <data> q;
	int i,j,k;
	if(map[x][y].vis[r])
		return;
	data t;
	t.x=x;t.y=y;t.g=r;
	q.push(t);
	map[x][y].vis[r]=1;
	map[x][y].ge[r]=color;
	while(!q.empty())
	{
		data p;
		p=q.front();
		q.pop();
		i=p.x;
		j=p.y;
		k=p.g;
		if(map[i][j].fuhao=='\\')
		{
			if(map[i][j].vis[(5-k)%4]==0)  //本格
			{
				q.push(d[i][j][(5-k)%4]);
				map[i][j].vis[(5-k)%4]=1;
				map[i][j].ge[(5-k)%4]=color;
			}
			if(0<=i+mo[k][0]&&i+mo[k][0]<m && 0<=j+mo[k][1]&&j+mo[k][1]<n)
			{
				if(map[i+mo[k][0]][j+mo[k][1]].vis[(k+2)%4]==0)
				{
					map[i+mo[k][0]][j+mo[k][1]].vis[(k+2)%4]=1;
					map[i+mo[k][0]][j+mo[k][1]].ge[(k+2)%4]=color;
					q.push(d[i+mo[k][0]][j+mo[k][1]][(k+2)%4]);
				}
			}
		}
		else
		{
			if(map[i][j].vis[3-k]==0)  //本格
			{
				q.push(d[i][j][3-k]);
				map[i][j].vis[3-k]=1;
				map[i][j].ge[3-k]=color;
			}
			if(0<=i+mo[k][0]&&i+mo[k][0]<m && 0<=j+mo[k][1]&&j+mo[k][1]<n)
			{
				if(map[i+mo[k][0]][j+mo[k][1]].vis[(k+2)%4]==0)
				{
					map[i+mo[k][0]][j+mo[k][1]].vis[(k+2)%4]=1;
					map[i+mo[k][0]][j+mo[k][1]].ge[(k+2)%4]=color;
					q.push(d[i+mo[k][0]][j+mo[k][1]][(k+2)%4]);
				}
			}
		}
	}
}
void init()
{
	int i,j,k;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
			for(k=0;k<4;k++)
			{
				map[i][j].vis[k]=0;
				map[i][j].fuhao=0;
				map[i][j].ge[k]=0;
			}
	}
}
int main()
{
	int i,j,k;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		getchar();
		//memset(map,0,sizeof(map));  //会超时
		init();
		color=0;
		white=0;
		for(i=0;i<m;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%c",&map[i][j].fuhao);
				for(k=0;k<4;k++)
				{
					d[i][j][k].x=i;
					d[i][j][k].y=j;
					d[i][j][k].g=k;
				}
			}
			
			getchar();
		}
		for(i=0;i<m;i++)
		{
			for(j=0;j<n;j++)
			{
				for(k=0;k<4;k++)
				{
					if(map[i][j].vis[k]==0)
					{
						color++;
						bfs(i,j,k);
					}
				}
			}
		}
		for(i=0;i<m;i++)
		{
			for(j=0;j<n;j++)
			{
				int flag=0,t=map[i][j].ge[0];
				for(k=1;k<4;k++)
				{
					if(t!=map[i][j].ge[k])
					{
						flag=1;
						break;
					}
				}
				if(!flag)
					white++;
			}
		}
		printf("%d\n",white);
	}
	return 0;
}

参考:http://blog.csdn.net/yan_____/article/details/8540924


, ,
  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。