BFSの笔记

例题一

WJ的逃离

当WJ醒来时，发现自己被困在一个地图的左上角，幸好WJ有张图，并了解到出口正是迷宫的右下角，至少有一条路径可以到达出口。
整个地图有些地方会有障碍（保证左上角右下角没有），WJ可以快速奔跑，只是需要拐弯时令人很不爽。为了保持心情愉悦，WJ想知道最少需要几次转弯。

思路：

是一个类似于最小路径的问题，要求最小的转弯次数，原理与最小步数问题相同，都是用bfs求解
在最小步数问题中，我们每次走四个方向或八个方向，每次只走一步，而这个问题求的是最少需要几次转弯，每次走一步显然不可以，每一次我们要走到路的尽头才行
来两个样例理解一下

5 5
0 0 0 * *
0 * 0 * *
0 * 0 0 0
0 * * * 0
0 0 0 0 0
1
2
3
4
5
6

1. 最小步数

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

这是最小步数的bfs标记，每次只标记一个

2. 最小转弯次数

0 0 0 * *
0 * 1 * *
0 * 1 2 2
0 * * * 3
0 1 1 1 1
1
2
3
4
5

这是最小步数的bfs标记，每次走到路得尽头再标记，显然，第一个标记到终点的地方一定是最小转弯次数，与最小步数相同

注意即使每次走一行或者走一列也要把走过的每个地方都标记上，不能只标记每行的行末
因为有可能在路径中间拐弯
例如：

5 5
0 0 0 * *
0 * * * *
0 0 0 0 0
0 * * * 0
0 * * * 0
1
2
3
4
5
6

#include
using namespace std;
       
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e6+10;
const int NN = 1e5+100;
const int pp = 1e9+7;
typedef pair<int,int>PII;
const int inf = 2147483647;

char c[505][505];
bool f[505][505];
queue<PII>q;
int a[505][505];
int n,m;

bool judge(int x,int y){
	if(x>=1&&y>=1&&x<=n&&y<=m&&c[x][y]!='*') return 1;
	return 0;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
		}
	}

	
	q.push({1,1});
	a[1][1]=-1;//第一次走不拐弯，所以初始化成 -1
	f[1][1]=1;//标记已走
	
	while(!q.empty()){
		int x1=q.front().fi,y1=q.front().se;
		q.pop();
		
		
		if(x1==n&&y1==m){
			cout<<a[x1][y1];
			return 0;
		}
		
		//走四个方向
		int xx=x1,yy=y1;
		
		while(judge(xx+1,yy)){
			xx++;
			if(xx!=x1&&!f[xx][yy]){
				q.push({xx,yy});
				f[xx][yy]=1;
				a[xx][yy]=a[x1][y1]+1;
			}		
		}
		
		xx=x1,yy=y1;
		
		while(judge(xx-1,yy)){
			xx--;
			if(xx!=x1&&!f[xx][yy]){
				q.push({xx,yy});
				f[xx][yy]=1;
				a[xx][yy]=a[x1][y1]+1;
			}
		}
			
		
		xx=x1,yy=y1;
		
		while(judge(xx,yy-1)){
			yy--;
			if(yy!=y1&&!f[xx][yy]){
				q.push({xx,yy});
				f[xx][yy]=1;
				a[xx][yy]=a[x1][y1]+1;
			}
		}
			
		
		xx=x1,yy=y1;
		
		while(judge(xx,yy+1)){
			yy++;
			if(yy!=y1&&!f[xx][yy]){
				q.push({xx,yy});
				f[xx][yy]=1;
				a[xx][yy]=a[x1][y1]+1;
			}
		}
	}	
}

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