搜索

BFS

概述

将当下遍历到的结点的子结点都入队列，只要队列不空，就不断令元素出队，由于先入队的先出队，此算法可以实现广度优先搜索

例题

1、迷宫最值

问题描述

n*m 的整型数地图，第一行和最后一行都是 0，从第一行任一点进入，出到第 n 行任一点，途中经过的最大数字为代价，求最小代价

代码逻辑

  • 利用BFS结合二分法求解

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool bfs(int x, int y, int ans)
   {
       queue<pair<int,int>> q;
       q.push(make_pair(x,y));
       visited[x][y] = true;
       while(!q.empty())
       {
           int xx = q.front().first, yy = q.front().second;
           for(int i=0;i<4;i++) //上下左右位移
           {
               int nx = xx + dx[i], ny = yy + dy[i];
               if(nx<1||nx>n||ny<1||ny>m||visited[nx][ny]||mp[nx][ny]>ans)
                   continue;
               if(nx==n)
                   return true;
               visited[nx][ny] = true;
               q.push(make_pair(nx,ny));
           }
       }
       return false;
   }

DFS

概述

  • 利用递归的特性实现深度优先算法

例题

1、淹没海岛

问题描述

N*N 的地图，’.’表示海洋，’#’表示陆地，数据保证第一行、第一列、最后一行、最后一列为海洋，联通的陆地视作同一个海岛，只有上下左右都是陆地的陆地才不被淹没，求被淹没的海岛数量

代码逻辑
  • 分别求出淹没前后的海岛数量，做减法就是答案
  • 一个地图存储初始数据，还有一个地图存储实行淹没后的数据，被淹没的陆地用另一个符号*来表示，dfs 实现淹没操作的时候就是把非.处修改为. 所以初始化淹没地图的时候不能把陆地直接改为.
  • 计算海岛数时，有一块陆地就把答案增 1 且 dfs 把与它相连的陆地都变成海洋
核心代码_计算海岛数量
1
2
3
4
5
6
7
8
9
10
11
for(int i=2;i<n;i++)
   {
       for(int j=2;j<n;j++)
       {
           if(mp[i][j]=='#')
           {
               ans++;
               dfs(i,j).
           }
       }
   }
核心代码_深搜
1
2
3
4
5
6
7
8
9
10
void dfs(int x, int y)
   {
    	mp[x][y] = '.';
       for(int i=0;i<4;i++)
       {
           int nx = x + dx[i], ny = y + dy[i];
           if(nx>1 && nx<n && ny>1 && ny<n && mp[nx][ny]!='.')
               dfs(nx,ny);
       }
   }

2、树上求和

问题描述

有 n 个结点 n-1 条边构成树，每个结点存一个整数（有正有负） 求最大和

代码逻辑
  • 对每一个结点都当作根结点应用 dfs 求得子树和的最大值，在所有结点的最大值中取最大的，由于要让每一个结点都作为根结点且走完整子树，所以这是 dfs 问题不是 bfs 问题
  • 利用 fath 参数防止走入父结点，dp 数组初始化为各结点存储的值
核心代码
1
2
3
4
5
6
7
8
9
10
11
void dfs(int cur,int fath)
   {
       dp[cur] = data[cur];
       for(int ver : edge[cur])
       {
           if(ver==fath)
               continue;
           dfs(ver,cur);
           dp[cur] += dp[ver] > 0 ? dp[ver] : 0;
       }
   }

记忆化搜索

概述

将过程答案记下，以此达到减枝的效果

特点

  • 往往是求约束条件下的方案数

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dfs(condition 1,condition 2,...)
  {
      if(dp[condition1][condition2]....!=初始化的值)
          return dp[condition1][condition2]....
      if(递归终点)  //根据限制条件求递归终点
          返回
      int ans = 0;
      else
      {
      	for(可走到的子结点) //超出限制条件的子结点忽略掉
              ans += dfs(子结点)
      }
      return dp[condition1][condition2]....=ans;
  }

例题

1、牛走草地

问题描述

N*M 的地图，#代表树，不可走，*代表草，可以走，走一次花费 1 时间，求从 x1，y1 走到 x2，y2 花费时间小于等于 t 的方案数

代码逻辑
  • dfs 中三个参数表示当下坐标和来到此处已经花费的时间
  • 限制条件是时间，时间达到了 T 必然不用接着尝试走下去了，如果到了终点，也可以走出终点再走回去，所以递归终点条件和有无到达终点无关
  • 只有不超出地图边界的子结点需要被考虑
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dfs(int x,int y,int time)
{
	if(dp[x][y][time]!=-1)
		return dp[x][y][time];
	if(time==T)
	{
		if(x==x_end&&y==y_end)
			return ans[x][y][time]=1;
		else
			return ans[x][y][time]=0;
	}

	int result=0;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||nx>N||ny<1||ny>M||mp[nx][ny]=='#')
			continue;
		result += dfs(nx,ny,time+1);
	}
	return dp[x][y][time]=result;
}

2、地宫取宝

问题描述

n*m 的地图从左上入，右下出，只能向右或者向下走。如果一件宝物大于手上宝物最大价值，那就选择拿它，当然也可以不拿，求抵达终点时手上恰好 k 件宝物的方案数

代码逻辑
  • dfs 四个参数表示当下坐标和手上已有宝物的最大价值和手上已有宝物的数量
  • 限制条件是宝物数量和终点限制，由于只能向右或向下，无法走回头路，所以到了终点必须停下，但是如果已经拿了 k 个物品，后面可以一路都不拿，所以物品限制不作为递归终点的判据
  • 只有不超出地图终点的子结点需要考虑，如果选择拿当下物品，到子结点时已经拿过的物品达到 num+1，只有 num+1<=k 的子结点需要考虑
核心代码
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
int dfs(int x, int y, int maxV, int num)
{

	if(dp[x][y][maxV][num] != -1)
	    return dp[x][y][maxV][num];
	if(x==n&&y==m)
	{
	    if(num==k || num==(k-1) && maxV<Map[x][y] )
	        return dp[x][y][maxV][num]=1;
	    else
	        return dp[x][y][maxV][num]=0;
	}

	int ans=0;
	if(x+1<=n)
	    ans += dfs(x+1,y,maxV,num);
	if(y+1<=m)
	    ans += dfs(x,y+1,maxV,num);

	if(Map[x][y]>maxV && x+1<=n && num<k)
		ans += dfs(x+1,y,Map[x][y],num+1);
	if(Map[x][y]>maxV && y+1<=m && num<k)
		ans += dfs(x,y+1,Map[x][y],num+1);

	return dp[x][y][maxV][num] = ans ;
}