搜索技术【广度优先搜索】 - 双向广度优先搜索 【HDU No. 3085】魔鬼II Nightmare Ⅱ

搜索技术【广度优先搜索】 - 双向广度优先搜索 【HDU No. 3085】魔鬼II Nightmare Ⅱ

双向搜索指分别从初始状态和目标状态出发进行搜索，在中间交会时即搜索成功。从一个方向搜索时，分支数会随着深度的增加而快速增长，产生一个大规模的搜索树。而双向搜索从两个方向搜索，产生两棵深度减半的搜索树，搜索速度更快。双向搜索包括双向DFS和双向广度优先搜索。

【HDU No. 3085】 魔鬼II Nightmare Ⅱ

杭电OJ 题目地址

【题意】

小明做了一个可怕的噩梦，梦见他和他的朋友分别被困在一个大迷宫里。更可怕的是，在迷宫里有两个魔鬼，他们会杀人。

小明想知道他能否在魔鬼找到他们之前找到他的朋友。小明和他的朋友可以朝四个方向移动。在每秒内，小明都可以移动3步，他的朋友可以移动1步。魔鬼每秒都会分裂成几部分，占据两步之内的网格，直到占据整个迷宫。假设魔鬼每秒都会先分裂，然后小明和他的朋友开始移动，如果小明或他的朋友到达一个有魔鬼的格子，就会死（新的魔鬼也可以像原来的魔鬼一样分裂）。

【输入输出】

输入：

输入以整数T 开头，表示测试用例的数量。

每个测试用例的第1行都包含两个整数n 和m （1

输出：

如果小明和他的朋友能够见面，则单行输出见面的最短时间，否则输出-1。

【样例】

【思路分析】

已知起点（小明）、终点（小明的朋友），两者在中间遇到即见面成功，可以采用双向广度优先搜索。

使用双向广度优先搜索时需要创建两个队列，分别从小明的初始位置、小明的朋友的初始位置开始，轮流进行广度优先搜索。在本题中，小明每次都可以移动3步，小明的朋友每次都可以移动1步，因此在每一轮循环中，小明都扩展3层，小明的朋友都扩展1层。在扩展时，需要检查与魔鬼的距离，判断该节点是否会被魔鬼波及。

【算法设计】

① 定义两个队列q[0]、q[1]，分别将小明的起始位置mm和小明的朋友的起始位置gg入队，秒数step=0。

② 如果两个队列均不空，则执行步骤3，否则返回-1。

③ step++，小明扩展3步，如果搜索到小明的朋友的位置，则返回true；否则小明的朋友扩展1步，如果搜索到小明的位置，则返回true。如果在两个方向搜索时发现有一个方向为true，则返回秒数step，否则执行步骤2。

【算法实现】

#include
#include
#include

using namespace std;
const int N = 805;

int n , m , step;
char mp[N][N];

int dir[4][2] = {{1, 0} , {-1, 0} , {0, 1} , {0, -1}};

struct node{
	
	int x, y;
	node(){}
	
	node(int x_ , int y_){
		
		x = x_;
		y = y_;
	}
}gg , mm , zz[2];

queue<node> q[2];

bool check(int x , int y){
	
	if(x < 0 || y < 0 || x >= n || y >= m || mp[x][y] == 'X'){
		
		return false;
	}
	
	for(int i = 0 ; i < 2; i++){
		
		if(abs(x - zz[i].x) + abs(y - zz[i].y) <= 2 * step){
			return false;
			
		}
	}
	
	return true;
}

int bfs(int t, int num , char st , char ed){
	
	queue<node> que = q[t];
	for(int k = 0; k < num ; k++){
		
		while(!que.empty()){
			
			node now = que.front();
			que.pop();
			
			q[t].pop();
			if(!check(now.x , now.y)){
				
				continue;
			}
			
			for(int j = 0 ; j < 4 ; j++){
				
				int fx = now.x + dir[j][0];
				int fy = now.y + dir[j][1];
				
				if(!check(fx , fy) || mp[fx][fy] == st){
					
					continue;
				}
				
				if(mp[fx][fy] == ed){
					
					return true;
				}
				
				mp[fx][fy] = st;
				q[t].push(node(fx , fy));
			}
		}
		
		que = q[t];
	}
	return false;
}

int solve(){
	
	while(!q[0].empty()){
		
		q[0].pop();
	}
	while(!q[1].empty()){
		
		q[1].pop();
	}
	
	q[0].push(mm);
	q[1].push(gg);
	
	step = 0;
	while(!q[0].empty() && !q[1].empty()){
		
		step ++;
		if(bfs(0 , 3 , 'M' , 'G') || bfs(1, 1, 'G' , 'M')){
			
			return step;
		}
	}
	
	return -1;
}

int main(){
	
	int T;
	scanf("%d", &T);
	
	while(T--){
		
		scanf("%d%d", &n , &m);
		for(int i = 0 ; i < n; i++){
			
			scanf("%s", mp[i]);
		}
		int cnt = 0;
		
		for(int i = 0; i < n ; i++){ //找出男/女/鬼 的位置 
			
			for(int j = 0 ; j < m ; j ++){
				
				if(mp[i][j] == 'Z'){
					
					zz[cnt].x = i , zz[cnt ++].y = j;
				}
				if(mp[i][j] == 'M'){
					
					mm.x = i , mm.y = j;
				}
				if(mp[i][j] == 'G'){
					
					gg.x = i , gg.y = j;
				}
			}
		}
		printf("%d\n" , solve());
	}
	
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151