小希的迷宫 HDU – 1272(广度优先搜索)

作者: zqqian 分类: ACM 发布时间: 2017-09-26 19:44
上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。Input输入包含多组数据,每组数据是一个以0 0结尾的整数对列表,表示了一条通道连接的两个房间的编号。房间的编号至少为1,且不超过100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。
Output对于输入的每一组数据,输出仅包括一行。如果该迷宫符合小希的思路,那么输出”Yes”,否则输出”No”。
Sample Input

6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0

-1 -1

Sample Output

Yes
Yes
No

这个题目别人的做法都是用并查集,但是我看到题目一开始想到的用是搜索来解决。

具体的思想就是 如果某个点被访问到了两次,那么就说明某个点有两条可以到达的路径,就输出No,否则就输出Yes.

这个题的数据范围是100000,用邻接矩阵肯定是不行了,只能用邻接表,这里我用的是vector。

还得有一个vis数组,与以往不同,这个vis数组保存的是哪个点访问的这个点。

然后就是最普通的BFS,注意先判断bfs的点是不是该点的的父节点。即不能从A点搜索到B点之后,又从B点搜索会A点去了。

判断这个以后还要判断搜索的新的借点是不是之前被搜索过。

这里需要注意的是有可能给你的是两块不联通的图,需要在输出的时候特别判断一下搜索过的点和输入的点数目是否相同。

还要特判 0 0 这个输入数据,特判为Yes,在这里卡了很长时间。。。。。

 

#include <iostream>
#include<cstring>
#include <queue>
#include<vector>

using namespace std;
int vis[100003];
int pre[100003];//用来记录点的数目
std::vector<int> v[100003];

int bfs(int x) {

	queue<int> q;
	int aa = x;
	q.push(aa);
	vis[x] = x;
	while(!q.empty()) {
		int t = q.front();
		q.pop();

		for(vector<int>::iterator it = v[t].begin(); it != v[t].end(); it++) {
			if(*it != vis[t]) {

				if(vis[*it] != 0) {

					return 0;
				} else {
					vis[*it] = t;
					q.push(*it);
				}
			}

		}
	}
	return 1;


}
int main() {
	int x, y;
	int xx
	int tot = 0;
	while(cin >> x >> y) {
		if (x == -1) {
			break;
		}
		if(x == 0 && y == 0) {
			int f = bfs(xx);    //从最后输入的那个点开始搜索

			for(int i = 1; i < 100003; i++) {     //判断是否存在没有搜索过的点
				if(pre[i] == 1 && vis[i] == 0) {

					f = 0;
				}
			}
			if(tot == 0)    //特判 0 0这组数据
				f = 1;
			if(f == 1) {
				cout << "Yes" << endl;
			} else {
				cout << "No" << endl;
			}
			memset(a, 0, sizeof(a));
			memset(vis, 0, sizeof(vis));
			memset(pre, 0, sizeof(pre));
			for(int i = 0; i < 100003; i++) {
				v[i].clear();
			}
			tot = 0;
			continue;
		}
		v[x].push_back(y);
		v[y].push_back(x);
		pre[x] = 1;
		pre[y] = 1;
		xx = x;
		tot++;
	}
	return 0;
}

 

一条评论
  • 小可爱

    2017年9月27日 下午10:30

    你好可爱啊,我可以啃你一口嘛

发表评论

电子邮件地址不会被公开。 必填项已用*标注