广度优先搜索（BFS）
广度优先搜索（BFS）
个人比较喜欢BFS（私人原因）
DFS和BFS比较：
1.BFS是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。这个时候不适宜使用DFS，因为DFS搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。（当然这个DFS的不足，可以使用迭代加深搜索ID-DFS去弥补）
2.空间优劣上，DFS是有优势的，DFS不需要保存搜索过程中的状态，而BFS在搜索过程中需要保存搜索过的状态，而且一般情况需要一个队列来记录。
3.DFS适合搜索全部的解，因为要搜索全部的解，那么BFS搜索过程中，遇到离根最近的解，并没有什么用，也必须遍历完整棵搜索树，DFS搜索也会搜索全部，但是相比DFS不用记录过多信息，所以搜素全部解的问题，DFS显然更加合适。
链接：https://www.zhihu.com/question/23780297/answer/167225829
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。
核心思想：第一个得到的解一定是最短的，最近的。（因为BFS是按照宽度搜索的）
大多数情况BFS和DFS都是可以的，但是要注意数据范围，防止爆栈的情况。
模板：
#include <iostream>
#include <queue>
using namespace std;
struct node
{
int x,y;
};
int w,h,sx,sy,sum;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
char map[25][25];
void BFS()
{
queue<node> q;
node n,p;
n.x = sx;
n.y = sy;
q.push(n);
map[sx][sy] = '#';
while(!q.empty())
{
n = q.front();
q.pop();
//sum++;
for(int i = 0;i < 4;i++)
{
int tx = n.x + dir[i][0];
int ty = n.y + dir[i][1];
//if(tx < 0 || tx >= w || ty < 0 || ty >= h)
//continue;
//if(map[tx][ty] == '#')
//continue;
if(tx >= 0 && tx < h && ty >= 0 && ty < w && map[tx][ty] == '.')
{
sum++;
p.x = tx;
p.y = ty;
q.push(p);
map[tx][ty] = '#';
}
}
}
}
int main()
{
int i,j;
//freopen("1.txt","r",stdin);
while(scanf("%d %d",&w,&h) == 2)
{
if(w == 0 && h == 0)
break;
for(i = 0;i < h;i++)
for(j = 0;j < w;j++)
{
cin >> map[i][j];
if(map[i][j] == '@')
{
sx = i;
sy = j;
}
}
sum = 1;
BFS();
printf("%d/n",sum);
}
return 0;
}、
话不多数，来题目：
Description
AveryBoy最近迷上了连连看游戏，于是他自己写了一个程序来玩，不过由于他学艺不精导致他写的连连看游戏连线不能从外面绕过。
游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。
Input
输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)，分别表示棋盘的行数与列数。
在接下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。
Output
每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。
Sample Input
3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3 2 3 0 0Sample Output
YES NO NO NO NO YESHINT
注意：询问之间无先后关系，都是针对当前状态的！
#include<bits/stdc++.h>
using namespace std;
int vis[1005][1005];
char mp[1005][1005];
int n,m;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct node
{
int x,y;
int c;
int cnt;
};
bool bfs(int sx,int sy,int ex,int ey)
{
memset(vis,0,sizeof vis);
if(mp[sx][sy]!=mp[ex][ey]) return false;
if(mp[sx][sy]=='0'||mp[ex][ey]=='0') return false;
node s,p;
vis[sx][sy]=1;
s.x=sx;
s.y=sy;
s.c=4;
s.cnt=0;
queue<node> q;
q.push(s);
while(!q.empty())
{
s=q.front();
q.pop();
if(s.x==ex&&s.y==ey&&s.cnt<=2)
{
return true;
}
if(s.cnt>2)
{
continue;
}
for(int i=0;i<4;i++)
{
int tx=s.x+dx[i];
int ty=s.y+dy[i];
if(tx<0||tx>=n||ty<0||ty>=m)
continue;
if(vis[tx][ty]==1)
continue;
if(mp[tx][ty]=='0'||mp[tx][ty]==mp[sx][sy])
{
p.x=tx;
p.y=ty;
if(i==s.c||s.c==4)
{
p.c=i;
p.cnt=s.cnt;
}
else
{
p.c=i;
p.cnt=s.cnt+1;
}
q.push(p);
vis[tx][ty]=1;
}
}
}
return false;
}
int main()
{
while(~scanf("%d%d",&n,&m)&&n!=0&&m!=0)
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>mp[i][j];
}
int q;
cin>>q;
while(q--)
{
int sx,sy,ex,ey;
cin>>sx>>sy>>ex>>ey;
if(bfs(sx-1,sy-1,ex-1,ey-1))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return 0;
}
Description
AveryBoy被困在一个n行m列的迷宫中了，问他能不能从起点到终点。迷宫中字符'.'表示该位置为空地，字符'*'表示该位置为障碍，他必须绕行，不过如果他转太多弯就会晕倒。假定给定的两个位置都是空地，初始时，AveryBoy所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。
Input
第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数，接下来为t组测试数据，每组测试数据中，
第1行为两个整数n, m (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来n行，每行包括m个字符。
每组测试数据的最后一行为5个整数k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示AveryBoy最多能转的弯数，(x1, y1), (x2, y2)表示起点和终点。
Output
每组测试数据对应为一行，若AveryBoy能从起点到终点，输出“yes”，否则输出“no”。
Sample Input
2 5 5 ...** *.**. ..... ..... *.... 1 1 1 3 1 5 5 ...** *.**. ..... ..... *.... 2 1 1 3 1Sample Output
no yes
#include<bits/stdc++.h>
using namespace std;
int vis[105][105];
char mp[105][105];
int k;
int sx,sy;
int ex,ey;
int n,m;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct node
{
int x,y;
int c;
int cnt;
};
bool bfs()
{
memset(vis,0,sizeof vis);
node s,p;
vis[sx][sy]=1;
s.x=sx;
s.y=sy;
s.c=4;
s.cnt=0;
queue<node> q;
q.push(s);
while(!q.empty())
{
s=q.front();
q.pop();
if(s.x==ex&&s.y==ey&&s.cnt<=k)
{
return true;
}
if(s.cnt>k)
{
continue;
}
for(int i=0;i<4;i++)
{
int tx=s.x+dx[i];
int ty=s.y+dy[i];
if(tx<0||tx>=n||ty<0||ty>=m)
continue;
if(mp[tx][ty]=='*')
continue;
if(vis[tx][ty]==1)
continue;
p.x=tx;
p.y=ty;
if(i==s.c||s.c==4)
{
p.c=i;
p.cnt=s.cnt;
}
else
{
p.c=i;
p.cnt=s.cnt+1;
}
q.push(p);
vis[tx][ty]=1;
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>mp[i][j];
}
cin>>k>>sx>>sy>>ex>>ey;
sx=sx-1;
sy=sy-1;
ex=ex-1;
ey=ey-1;
if(bfs())
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
return 0;
}
Description
这次AveryBoy被困在一个三维迷宫中，他必须想办法在T分钟内离开迷宫（包括T）。迷宫是一个A*B*C的立方体，起点在（0，0，0）位置，终点在（A-1，B-1，C-1）位置。如果他能离开迷宫，输出离开迷宫所需最短时间，否则输出-1。
Input
输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表迷宫的大小和离开的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块......),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙.
Output
对于每组测试数据,如果AveryBoy能离开迷宫,那么请输出他最少需要多少分钟,否则输出-1.
Sample Input
1 3 3 4 20 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0Sample Output
11
#include<bits/stdc++.h>
using namespace std;
int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int vis[55][55][55];
char mp[55][55][55];
int a,b,c;
int T;
int cnt=0;
struct node
{
int x,y,z;
int step;
};
bool bfs()
{
memset(vis,0,sizeof vis);
cnt=0;
node s,p;
queue<node> q;
s.x=0;
s.y=0;
s.z=0;
s.step=0;
vis[0][0][0]=1;
q.push(s);
while(!q.empty())
{
s=q.front();
q.pop();
if(s.x==a-1&&s.y==b-1&&s.z==c-1&&s.step<=T)
{
cnt=s.step;
return true;
}
if(s.step>T)
{
continue;
}
for(int i=0;i<6;i++)
{
int tx=s.x+dx[i];
int ty=s.y+dy[i];
int tz=s.z+dz[i];
if(tx<0||tx>=a||ty<0||ty>=b||tz<0||tz>=c)
continue;
if(mp[tx][ty][tz]=='1')
continue;
if(vis[tx][ty][tz]==1)
continue;
p.x=tx;
p.y=ty;
p.z=tz;
p.step=s.step+1;
q.push(p);
vis[tx][ty][tz]=1;
}
}
return false;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>a>>b>>c>>T;
for(int i=0;i<a;i++)
for(int j=0;j<b;j++)
for(int k=0;k<c;k++)
{
cin>>mp[i][j][k];
}
if(bfs())
cout<<cnt<<endl;
else
cout<<-1<<endl;
}
return 0;
}
路过的大佬能不能对八数码问题的理解和康托展开
上一篇： 广度优先搜索（BFS）
下一篇： BFS --- 广度优先搜索