搜索
找啊找啊找朋友
枚举
子集枚举
广度优先搜索
深度优先搜索
启发式搜索
迭代加深搜索
1. 广搜BFS
广度优先搜索是一种分层的查找过程,每向前一层可能会访问一批顶点,不像深度优先搜索有回溯的过程。
同时与深搜用栈来维护不同,广搜一般是用先进先出队列来进行维护的。
实际上我们从初始状态开始,搜索第k层的意义就是,搜索需要k步才能到达的状态。**
广度优先搜索——具体操作、特点
具体操作:
它是先将起始状态加入队列,然后每次从队列中取出一个状态,将其后继状态加入队列,后继状态指的是由当前状态一步操作可以到达的状态,直到所有状态均被访问为止。
特点:
1:它并不考虑结果的可能位置,而是彻底地搜索所有状态,所以很少有基于 BFS 的启发式算法,也很少对 BFS 进行剪枝。
2:相对于 DFS,BFS 更加难于保存当前节点的状态,所以 BFS 在爆搜中的应用较少。
3:在某一层还没有搜索完时,是不会进入下一层的,也就是说在队列中所有同一深度的状态,是连续的一段。
(这个性质在之后会用到!)
广度优先搜索——算法框架
广搜主要解决的是最优问题,比如最短路径,最少步数等。
void bfs(v){
Int queue(q);
visited[v]=true; Insert_queue(q,w);
While not empty(q) do {
取出队首元素 v,Visite(v);
delete_queue(q,v);//队首元素出队
For 对所有v扩展出来的元素w{
if (not visited[w] )
{visited[w]=true; Insert_queue(q,w);}
}
}
经典问题1——湖计数-洛谷 P1596
由于降雨,雨水汇集在田地。用 ???? × ????(1 ≤ ????, ???? ≤ 100) 网格图 表示。每个网格中有水(W) 或是旱地(.)。
一个网格与周围八个网格相连,而一组相连的网格视为一个水坑。 给出约翰田地的示意图,确定当中有多少水坑。
9 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
const int dx[8]= {-1,1,0,0,-1,1,-1,1};
const int dy[8]= {0,0,-1,1,-1,1,1,-1};
char g[maxn][maxn];
bool vis[maxn][maxn];
int n,m,cnt;
struct node {
int x,y;
} cur,nxt;
queue<node>q;
void bfs(int x,int y) {
vis[x][y]=1;
q.push({x,y});
while(q.size()) {
cur=q.front();q.pop();//取队首元素,队首元素出队。
for(int i=0; i<8; i++) {
int xx=cur.x+dx[i], yy=cur.y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]=='W'&&vis[xx][yy]==0) {
vis[xx][yy]=1;
q.push({xx,yy});
}
}
}
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
cin>>g[i][j];
}
int cnt=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(vis[i][j]==0&&g[i][j]=='W') {
bfs(i,j);
cnt++;
}
cout<<cnt<<endl;
return 0;
}
经典问题2——走迷宫 OPENJUDGE2573
一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走
n,m<=1000
举个例子:一个5*5的迷宫,左上到右下
5 5
..###
#....
#.#.#
#.#.#
#.#..
.为走出迷宫的路线。
还是套用最开始给出的bfs的方法。
最开始将初始坐标加入队列,然后每一次取出队首,扩展相邻没有遍历到过的点,然后加入队列中。
如果某一时刻我们发现走出了网格了,那么直接输出当前的步数即可。
BFS的优势,先找到的就是最小的!!!
如果队列空了,还是没有走出网格,说明无解,输出-1。
如何找最小步数?
只记录走过的坐标行吗?补充什么信息?
坐标+步数!
开3各单独的队列或者用一个结构体队列。
自己打码
问题3——迷宫升级-1-01迷宫
https://www.luogu.com.cn/problem/P1141
有一个仅由数字 01 组成的 n×n 格迷宫。01可以相互四个方向移动。
对于给定的迷宫,m次询问从某一格开始能移动到多少个格子(包含自身)。
1≤n≤1000,1≤m≤100000
1次询如何解决?
用1次询问的方法可以解决m次询问的问题吗?
如何解决m次询问的问题?
超时!
重复计数,如何解决?
记下来。
BFS时候记录了所有同一联通块所有的点。记录并计数完成后
方法一:再返回记录每一个格子连通块总数。
方法二:记录起始点的格子数,所有接点记录其起始结点是谁,询问的时候,直接查询起始点所在的格子。(明天要学的并查集的概念)
自己打码
问题4-迷宫升级-2-鸣人和佐助
http://noi.openjudge.cn/ch0205/6044/
已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费1个单位时间,打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了,则只可以走到没有大蛇丸手下的位置,不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动,大蛇丸的手下也不移动。请问,鸣人要追上佐助最少需要花费多少时间?
http://noi.openjudge.cn/ch0205/6044/
除了坐标信息,还有查克拉限制,如何解决?
来的早,查卡拉少可能有的手下打不死
来的晚,查克拉多,可能更好。
队列需要哪些信息?如何打标记?
维护点的信息,除了坐标外,还有查克拉大小,我们关注的是到xy点有z个查克拉的时候走了几步。
http://noi.openjudge.cn/ch0205/6044/
维护坐标和查克拉三维信息,队列记录坐标查克拉和步数。
根据不同的坐标点分析变化,在坐标和查卡拉相同的情况下只需要记录最小步数。
if(mp[di][dj]=='#'&&dc>0) {
dc=dc-1;
if(vis[di][dj][dc])continue;
vis[di][dj][dc]=1;
x.push(di),y.push(dj),s.push(ds),c.push(dc);
} else {
if(mp[di][dj]!='#'&&dc>=0){
if(vis[di][dj][dc])continue;
vis[di][dj][dc]=1;
x.push(di),y.push(dj),s.push(ds),c.push(dc);
}
问题5-迷宫升级-3-4980:拯救行动
http://noi.openjudge.cn/ch0205/4980/
公主被恶人抓走,被关押在牢房的某个地方。牢房用N*M (N, M <= 200)的矩阵来表示。矩阵中的每项可以代表道路(@)、墙壁(#)、和守卫(x)。
英勇的骑士(r)决定孤身一人去拯救公主(a)。我们假设拯救成功的表示是“骑士到达了公主所在的位置”。由于在通往公主所在位置的道路中可能遇到守卫,骑士一旦遇到守卫,必须杀死守卫才能继续前进。
现假设骑士可以向上、下、左、右四个方向移动,每移动一个位置需要1个单位时间,杀死一个守卫需要花费额外的1个单位时间。同时假设骑士足够强壮,有能力杀死所有的守卫。
如何解决?步数+2?
现在所学:BFS只能解决步数为1的最短路问题?
怎么变为步数1?
拆点,把移动到格子和杀死守卫分开入队。
自己打码
问题6-迷宫升级-4-带传送门的迷宫
****P1825 [USACO11OPEN] Corn Maze S
迷宫里有一些传送装置,可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。如果一头奶牛处在这个装置的起点或者终点,这头奶牛就必须使用这个装置。
玉米迷宫除了唯一的一个出口都被玉米包围。
1.玉米,# 表示,这些格子是不可以通过的。
2.草地,. 表示,可以简单的通过。
3.传送装置,每一对大写字母 A 到 Z表示。
4.出口,= 表示。
5.起点, @ 表示
如何处理传送门?
如果一头奶牛处在这个装置的起点或者终点,这头奶牛就必须使用这个装置。=>传送门必须做
每对传送门只能用一次 A1-A2, A2-A1,还是可以打访问标记的。
自己打码
问题7-倒水问题
****P1432 倒水问题
假定两个水壶A和B,供水量不限。可以使用三种方法装水:
给一个水壶装水;
把一个水壶倒空;
从一个水壶倒进另一个水壶。
当从一个水壶倒进另一个水壶时,如果第一个水壶倒空,或者第二个水壶装满就不能再倒了。例如,一个水壶A是5加仑和另一个水壶B是6加仑,水量是8加仑,则从水壶A倒进水壶B时,让水壶B充满水而水壶A剩3加仑水。
问题由3个参数:Ca,Cb和N,分别表示水壶A和B的容量,目标水量N。解决问题的目标是,给出一系列倒水的步骤,使水壶B中的水量恰好是N。
https://www.luogu.com.cn/problem/P1432
有两个无刻度标志的水壶,分别可装 x 升和 y 升 ( x,y 为整数且均不大于 100 )的水。设另有一水 缸,可用来向水壶灌水或接从水壶中倒出的水, 两水壶间,水也可以相互倾倒。已知 x 升壶为空 壶, y 升壶为空壶。问如何通过倒水或灌水操作, 用最少步数能在x或y升的壶中量出 z ( z ≤ 100 )升的水 来。
输入描述 Input Description
一行,三个数据,分别表示 x,y 和 z;
输出描述 Output Description
一行,输出最小步数 ,如果无法达到目标,则输出”impossible”
样例输入 Sample Input
3 22 1
样例输出 Sample Output
14
题目分析:隐式图问题
设某一时刻a杯子中有x升水,b杯子有y升水,经过了step步,我们称此时的状态为(x , y , step)。在这里所谓的状态就是说某一个时刻,各个杯子的水的量。我们可以将状态做为节点,那么一个节点的后继节点也就是当前状态通过倒水操作,转化到另一个状态。
因此可以用bfs搜索。同样我们需要明确状态间的转化,换句话说,就是如何去计算一个节点的后继节点。
对于状态(x, y,z) 可能的后继状态有如下几种:
X倒空,x倒满,y倒空,y倒满,
x倒向y(x有剩余,x无剩余二选一) y倒向x(y有剩余,y无剩余二选一)
同时需要判断状态是否已经出现过,如果未出现,则入对列即可。
判重:状态是否出现过,通过二维数组,判断xy的水量是否出现过。
程序实现技巧
!千万别写8各if,写一个函数
void inser(int tx,int ty,int tstep){
if(tx<0||ty<0||tx>x||ty>y) return;
if(v[tx][ty]) return;
tail++;
qx[tail]=tx; qy[tail]=ty; qstep[tail]=tstep;
v[tx][ty]=1;
}
例题
洛谷 P1596:湖计数
OPENJUDGE2573:走迷宫
Openjudge:6044:鸣人和佐助
Openjudge 4980:拯救行动
洛谷 P1825 [USACO11OPEN] Corn Maze S
洛谷1432倒水问题
洛谷 P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱
洛谷 P2346 四子连棋
orz
stOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
Orz
Orz
%%%%%%%%%%%%%%%
突然发现这例题我都还没做(
话说 OpenJudge 是啥?
CSP-J 前复习下搜索
加油Orz
经典问题——湖计数那题不用 vis 数组吧,访问过一个节点后直接把这个节点改成
.
就行了#include<bits/stdc++.h> const int dx[8]={-1,-1,-1,0,0,1,1,1}; const int dy[8]={-1,0,1,-1,1,-1,0,1}; using namespace std; const int N=100; char g[N][N]; int n,m,cnt; void dfs(int x,int y) { g[x][y]='.'; for (int i=0;i<8;i++) { int vx=x+dx[i],vy=y+dy[i]; if (vx<0||vx>=n||vy<0||vy>=m) continue; if (g[vx][vy]^'.') dfs(vx,vy); } } int main() { scanf("%d%d",&n,&m); for (int i=0;i<n;i++) for (int j=0;j<m;j++) cin>>g[i][j]; for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (g[i][j]=='W') dfs(i,j),cnt++; printf("%d",cnt); return 0; }
Orz