DFS和BFS算法的应用

深度优先算法（DFS）和广度优先算法（BFS）都是经典的搜索算法，下面我们主要来讨论一下它们使用场景的不同：

• BFS适合用来搜索最优解。因为BFS搜索过程中遇到的解一定离根是最近的，此时算法即可终止，降低了时间复杂度。
• DFS适合用来搜索全部的解，因为DFS的基本逻辑是将全局搜索完毕之后从其中找出离根最近的解，BFS的优势就没有了。
• 在空间复杂度上DFS是优于BFS的，这是因为DFS不需要队列来保存搜索过的状态。

P1219 [USACO1.5] 八皇后 Checker Challenge

题目描述

一个如下的 $6 \times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 $2\ 4\ 6\ 1\ 3\ 5$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：

行号 $1\ 2\ 3\ 4\ 5\ 6$

列号 $2\ 4\ 6\ 1\ 3\ 5$

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 $3$ 个解。最后一行是解的总个数。

输入格式

一行一个正整数 $n$，表示棋盘是 $n \times n$ 大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

输入输出样例 #1

输入 #1

6

输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

说明/提示

【数据范围】
对于 $100\%$ 的数据，$6 \le n \le 13$。

题目翻译来自NOCOW。

USACO Training Section 1.5

解决方案

这道题显然需要我们找到所有可能的情况并判断其中哪些情况符合要求，所以我们的基本思路应该是DFS。

此外，由于在一个格子上沿八个方向的搜索效率较低，我们应该逐行进行横向搜索。

count = 0

def dfs(x):
  global count
  # 搜索函数的开头应该先明确推出条件
  # 这里是当前搜索的行数超出棋盘搜索即终止
  if x > n:
    if count <= 2:
      for i in range(1, n+1):
        print(a[i], end=" ")
      print("")
    count += 1
    return

  # 然后开始实现搜索功能
  for y in range(1, n+1):
    # 在上对角线及其平行线上的点的横纵坐标之和相等
    # 在下对角线及其平行线上的点的横纵坐标之差相等
    if b[y] == 0 and c[x+y] == 0 and d[x-y+n] == 0:
      a[x] = y
      b[y] = 1
      c[x+y] = 1
      d[x-y+n] = 1

      # 开始搜索下一行
      dfs(x+1)

      # 还原
      b[y] = 0
      c[x+y] = 0
      d[x-y+n] = 0


if __name__ == "__main__":
  n = int(input())

  # a, b, c, d四个数组分别用来存储行、列、上对角线和下对角线中的数据
  a, b, c, d = [0] * 50, [0] * 50, [0] * 50, [0] * 50

  # 记录解的总数
  dfs(1)

  print(count)

Bingo！

P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱

题目描述

小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 $N \times N$ 个格子组成的二维迷宫。

小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。

每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。

迷宫中有些格子小明可以经过，我们用 . 表示；

有些格子是墙壁，小明不能经过，我们用 # 表示。

此外，有些格子上有陷阱，我们用 X 表示。除非小明处于无敌状态，否则不能经过。

有些格子上有无敌道具，我们用 % 表示。

当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 $K$ 步。

之后如果再次到达该格子不会获得无敌状态了。

处于无敌状态时，可以经过有陷阱的格子，但是不会拆除 / 毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。

给定迷宫，请你计算小明最少经过几步可以离开迷宫。

输入格式

第一行包含两个整数 $N$ 和 $K$。$(1 \le N \le 1000，1 \le K \le 10)$。

以下 $N$ 行包含一个 $N\times N$ 的矩阵。

矩阵保证左上角和右下角是 .。

输出格式

一个整数表示答案。如果小明不能离开迷宫，输出 $-1$。

输入输出样例 #1

输入 #1

5 3
...XX
##%#.
...#.
.###.
.....

输出 #1

10

输入输出样例 #2

输入 #2

5 1
...XX
##%#.
...#.
.###.
.....

输出 #2

12

说明/提示

时限 3 秒, 256M。蓝桥杯 2018 年第九届国赛

解决方案

这道题显然要求的是一个最优的最短路径，所以我们大胆采用BFS即可，只需要对其中的条件写一个约束即可。

import sys
from collections import deque

dirs = [(-1, 0), (0, -1), (0, 1), (1, 0)]

def bfs(n, k, arr, vis):
  # bfs先创建一个队列
  queue = deque()
  queue.append((0, 0, 0, 0))
  vis[0][0] = 0

  while queue:
    x, y, step, magic = queue.popleft()

    # 还是先写退出条件
    if x == n-1 and y == n-1:
      return step

    # 开始搜索
    for dx, dy in dirs:
      nx, ny = x+dx, y+dy

      if not(0 <= nx < n and 0 <= ny < n):
        continue
      if arr[nx][ny] == '#':
        continue
      if arr[nx][ny] == 'X' and magic == 0:
        continue

      new_magic = max(0, magic-1)
      if arr[nx][ny] == '%':
        new_magic = k

      # 剪枝，这里将没有当下情况好的情况全部剪掉
      # 时间复杂度得以大幅降低
      if vis[nx][ny] < new_magic:
        vis[nx][ny] = new_magic
        queue.append((nx, ny, step+1, new_magic))

  return -1

if __name__ == "__main__":
  n, k = map(int, input().split())
  # 使用sys.stdin.readline()来加快读取速度
  arr = [sys.stdin.readline().strip() for _ in range(n)]
  # 使用vis数组来记录每个点剩余的无敌时间
  vis = [[-1 for _ in range(n+1)] for __ in range(n+1)]

  ans = bfs(n, k, arr, vis)
  print(ans)

Bingo!