BFS

BFS记录路径

BFS记录路径

Posted by zhangmh on 2021-11-22
Estimated Reading Time 11 Minutes
Words 2.2k In Total
Viewed Times

前段时间学完BFS很开心地发现oj上有些题可以做了！但是记录路径又把我难住了，，，赶紧去学习一下，本篇算是复习BFS和它的记录路径方法吧。

还是以题引例：1086 迷宫问题 1220 Look for homework 1654 Treasure House

以1654为例：

1654 Treasure House

选这个题是因为学这种方法的时候就是做的这个题啦 :P（才不是因为要把师哥挂出来orz）

img点击并拖拽以移动

大概意思就是说给定n*m的矩阵，矩阵由字符$和#组成，$位置可以走，#不能走，求左上角到右下角的最短路程并按照字典序最大输出路径。

很显然搜索方法使用BFS，即模拟队列方法搜索，广度优先寻找最短路径，但是需要找出最短路径，我们使用的方法是另开结构体存路径。

下面根据代码理解叙述：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
using namespace std;
typedef long long ll;
#define maxn 10000005
#define INF 0x3f3f3f3f
const int mod=1e9+7;
//多组输入记得每次循环之前初始化（数组，栈，队列，某些变量）！！！
const int N=13;
char c[N][N];
int n,m,x,y;
int ans,cnt;
int head,end;
bool vis[N][N];
int dx[4]={0,1,-1,0};
int dy[4]={-1,0,0,1};
char dir[N][N];
int val[N][N];

定义变量部分，注意方向数组dx[4]和dy[4]，初始化值时有很大讲究，因为我们要按照字典序最大输出，所以按照字典序四个方向应为W,S,N,E，按照上北下南左西右东（废话）给两个数组一一对应赋值（千万看仔细，如果搞错了就肯定WA）。

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
struct node
{
	int x,y,time;
	node(){};
	node(int xx,int yy,int tt)
	{
		x=xx,y=yy,time=tt;
	}
};

struct direction//记录方向所用数组，因记录字母用字符型，dir来记录字符变量 
{
	int x,y,time;
	char dir;
	direction(){};
	direction(int xx ,int yy,int tt,char dd)
	{
		x=xx,y=yy,time=tt,dir=dd;
	}
} e[100][100];

bool check(int xx,int yy)//地图问题必有操作：判断是否可以走 
{                        //即既不越界，也是可以走的方格 
	if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&c[xx][yy]!='#') return true;
	else return false;
}

bool bfs()
{
	queue<node>q;
	node s(1,1,0);
	vis[1][1]=1;
	q.push(s);
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		if(now.x==n&&now.y==m)
		{
			ans=now.time;
			return true;
		}
		for(int i=0;i<4;i++)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];
			if(check(nx,ny)&&!vis[nx][ny])
			{
				node nex(nx,ny,now.time+1);
				vis[nx][ny]=true;
				e[nx][ny].x=now.x;//可以发现这里存的是上一步的坐标，因为我们要找出最终最短路径，广度优先会存有很多条路径，
				e[nx][ny].y=now.y;//一旦符合我们条件即可以走到最后一步的路径为最佳路径，那么这条路径的前一步一定是最终路径上的一步 
				e[nx][ny].time=now.time+1;
				if(i==0)
				e[nx][ny].dir='W';
				else if(i==1)
				e[nx][ny].dir='S';
				else if(i==2)
				e[nx][ny].dir='N';
				else if(i==3)
				e[nx][ny].dir='E';//那么我们前面按照字典序初始化定义dx dy数组的作用可以体现了，
				q.push(nex);      //按照i递增顺顺序，最后输出一定为最大字典序 
			}
		}
	}
	return false;
}

void print(int a, int b)
{
    if(a==1&&b==1) return;//定义输出函数，只要可以从最后坐标推到第一个坐标的即答案路径，输出 
    print(e[a][b].x, e[a][b].y);//递归调用函数 
    printf("%c", e[a][b].dir);
}

自定义函数部分，详细解释在代码中（语文学得不好，如果有些话讲的不对劲请见谅 ^_^ ）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
	//freopen("test.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		cin>>c[i][j];
		}
	}
	bfs();
	printf("%d\n", e[n][m].time);
    print(n, m);
    printf("\n");
	return 0;
}

主函数部分，调用了bfs（）、print（）两个函数。

1220 Look for homework

这个题我做的时候觉得很坑，因为你会发现输入的数字之间莫得空格，那么输入的是字符串，不能定义int数组。。。结果另一个同学做的时候完全没被这个点绊到，，，是我太菜了QAQ

这个题是最小字典序，和上面那个题不一样了哦

下面放AC代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
using namespace std;
typedef long long ll;
#define maxn 10000005
#define INF 0x3f3f3f3f
const int mod=1e9+7;
//多组输入记得每次循环之前初始化（数组，栈，队列，某些变量）！！！
const int N=13;
char a[N][N];
int n,m,x,y;
int ans,cnt;
int head,end;
bool vis[N][N],ac[N][N];
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};

struct node
{
	int x,y,step;
	node(){};
	node(int xx,int yy,int ss)
	{
		x=xx,y=yy,step=ss;
	}
};

struct direction
{
	int x,y,step;
	char dir;
	direction(){};
	direction(int xx,int yy,int ss,char dd)
	{
		x=xx,y=yy,step=ss,dir=dd;
	}
} e[100][100];

bool check(int xx,int yy)
{
	if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]!='1') return true;
	else return false;
}

bool bfs()
{
	queue<node>q;
	node s(1,1,0);
	vis[1][1]=1;
	q.push(s);
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		if(now.x==n&&now.y==m)
		{
			ans=now.step;
			return true;
		}
		for(int i=0;i<4;i++)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];
			if(check(nx,ny)&&!vis[nx][ny])
			{
				node nex(nx,ny,now.step+1);
				vis[nx][ny]=true;
				e[nx][ny].x=now.x;
				e[nx][ny].y=now.y;
				e[nx][ny].step=now.step+1;
				if(i==0)
				e[nx][ny].dir='D';
				else if(i==1)
				e[nx][ny].dir='L';
				else if(i==2)
				e[nx][ny].dir='R';
				else if(i==3)
				e[nx][ny].dir='U';
				q.push(nex);
			}
		}
	}
	return false;
}

void print(int a,int b)
{
	if(a==1&&b==1) return;
	print(e[a][b].x,e[a][b].y);
	printf("%c", e[a][b].dir);
}

int main()
{
	//freopen("test.in","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
    	memset(a,0,sizeof(a));//多组输入一定记得每次输入前初始化！ 
    	memset(vis,0,sizeof(vis));
    	for(int i=1;i<=n;i++)
        {
        	for(int j=1;j<=m;j++)
    	    {
    		    cin>>a[i][j];
		    }
 	    }
	bfs();
	printf("%d\n", e[n][m].step);
        print(n, m);
        printf("\n");
	}
    
	
	return 0;
}

1086 迷宫问题

这个题比较不同的是输出的是坐标，注意格式，有空格的地方一定带空格，一般直接复制输出样例再改一下数字就好了。这个题简单一些，题目告诉了有唯一解，直接输出记录最短路径即可。注意这个地方给定左上角为（0,0），别写成（1,1）！！！

AC代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
using namespace std;
typedef long long ll;
#define maxn 10000005
#define INF 0x3f3f3f3f
const int mod=1e9+7;
//多组输入记得每次循环之前初始化（数组，栈，队列，某些变量）！！！
int a[5][5];
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
int ans;
bool vis[5][5];

bool check(int xx,int yy)
{
	if(xx>=0&&xx<5&&yy>=0&&yy<5&&a[xx][yy]!=1) return true;
	else return false;
}

struct node
{
	int x,y,step;
	node(){};
	node(int xx,int yy,int ss)
	{
		x=xx,y=yy,step=ss;
	}
};

struct process
{
	int x,y;
} e[100][100];

bool bfs()
{
	queue<node>q;
	node s(0,0,0);
	vis[0][0]=true;
	q.push(s);
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		if(now.x==4&&now.y==4)
		{
			ans=now.step;
			return true;
		}
		for(int i=0;i<4;i++)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];
			if(check(nx,ny)&&!vis[nx][ny])
			{
				node nex(nx,ny,now.step+1);
				e[nx][ny].x=now.x;
				e[nx][ny].y=now.y;
				vis[nx][ny]=true;
				q.push(nex);
			}
		}
	}
	return false;
}

void print(int a,int b)
{
	if(a==0&&b==0)
	{
		printf("(0, 0)\n");
		return;
	}
	print(e[a][b].x,e[a][b].y);
	printf("(%d, %d)\n",a,b);
}

int main()
{
	//freopen("test.in","r",stdin);
    for(int i=0;i<5;i++)
    {
    	for(int j=0;j<5;j++)
    	{
    		cin>>a[i][j];
		}
	}
	bfs();
	print(4,4);
	return 0;
}

打败遗忘最好的方法是多复习多做类似题！多复习多复习~

如有错误请赐教 Orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
BFS
FRIENDS
ESC