题目描述

洛谷P1649

一、题目理解

首先，我们来看一下这道题目的要求。题目给定了一个 N×N（1≤N≤100） 的方格，方格中的每个格子有不同的状态，用 . 表示可以行走的格子，x 表示不能行走的格子，并且有起始点 A 和终点 B。我们要控制一个角色（比如题中的卡门或者贝西）从 A 点走到 B 点，这个角色因为自身特点不好转弯，只能沿着方格的边平行移动（也就是上下左右四个方向），然后求出从 A 到 B 最少要转 90 度弯的次数。如果无法到达终点，那就输出 -1。

二、整体解题思路

方案一

（一）初始化相关数据结构

1. 记录方格状态：
   我们首先创建一个字典 vis，用于记录方格中每个位置是否被访问过以及是否是障碍物。遍历整个 N×N 的方格，如果某个位置对应的字符是 x，那就把该位置在 vis 字典中标记为 1（表示不可访问，相当于障碍物），如果是 . 则标记为 0（表示可访问）。例如，对于下面这样一个简单的 3×3 方格示例：

. x A
. . .
B x .

我们会根据其内容初始化 vis 字典，像 (0, 0) 位置对应 .，vis[(0, 0)] 就会被初始化为 0，而 (0, 1) 位置对应 x，vis[(0, 1)] 就会被初始化为 1。
2. 定义移动方向：
定义一个列表 move，里面包含四个元组 [(1, 0), (0, -1), (-1, 0), (0, 1)]，分别对应向下、向左、向上、向右这四个方向的坐标偏移量。例如，当前位置是 (i, j)，如果按照 (1, 0) 这个方向移动，下一个位置就是 (i + 1, j)，也就是向下移动一格。

（二）使用队列进行 BFS

1. 队列初始化及起始点入队：
   创建一个队列 q（这里使用 Python 的 queue.Queue），然后把起始点相关的信息放入队列。起始点信息包含起始位置坐标（也就是 start，它是一个二元组，比如 (i, j) 形式表示在方格中的位置），还有当前转弯次数（初始化为 0）以及当前的方向（初始化为 None，因为刚开始出发方向还不确定），整体就是 start + (0, None) 这样的形式放入队列 q 中，同时把起始点在 vis 字典中标记为已访问（vis[start] = 1）。
2. 循环进行搜索：
   只要队列 q 不为空，就持续进行循环搜索。每次从队列中取出一个元素，这个元素包含当前位置、转弯次数以及当前方向等信息，我们记为 now，从中提取出当前位置 cur_pos 和当前方向 cur_dir。
3. 判断是否到达终点：
   如果当前位置 cur_pos 就是终点 end，那就意味着找到了一条从起点到终点的路径，把当前的转弯次数记录下来（也就是 now[2]）作为答案，然后跳出循环。
4. 探索相邻位置：
   如果还没到达终点，那就遍历所有可能的移动方向（也就是前面定义的 move 列表中的四个方向）。对于每个方向 dir，计算按照这个方向移动后的新位置 new_pos，同时计算新的转弯次数 newstep。如果当前方向 cur_dir 是 None（也就是刚开始出发，还没确定方向）或者新方向 dir 和当前方向 cur_dir 不一样，那就意味着要转弯了，需要把转弯次数 newstep 加 1。
   然后，只要新位置 new_pos 在方格范围内（也就是 0 <= new_pos[0] < n 且 0 <= new_pos[1] < n）并且该位置不是障碍物（vis.get(new_pos, 0) == 0），就把这个新位置标记为已访问（vis[new_pos] = 1），然后把新位置以及更新后的转弯次数、新方向这些信息作为一个整体（也就是 new_pos + (newstep, dir)）放入队列 q 中，接着继续沿着这个方向探索下一个位置（也就是更新 new_pos，继续 new_pos = (new_pos[0] + dir[0], new_pos[1] + dir[1]) 这样移动），直到遇到边界或者障碍物为止。

（三）处理最终结果

最后，如果找到了从起点到终点的路径（也就是 ans 不等于 -1），按照题目要求需要把记录的转弯次数减 1（因为在放入队列时，初始的转弯次数是 0，而第一次移动时如果转弯了才开始计数，所以最后要减 1）返回；如果没有找到路径，那就直接返回 -1。

代码实现

import queuedef find_min_turns(n, start, end, board):vis = {}for i in range(n):for j in range(n):if board[i][j] == 'x':vis[(i, j)] = 1else:vis[(i, j)] = 0move = [(1, 0), (0, -1), (-1, 0), (0, 1)]q = queue.Queue()q.put(start + (0, None))vis[start] = 1  ans = -1while not q.empty():now = q.get()cur_pos = now[:2]if cur_pos == end:ans = now[2]breakelse:cur_dir = now[3]for dir in move:new_pos = (cur_pos[0] + dir[0], cur_pos[1] + dir[1])newstep = now[2]if cur_dir is None or dir!= cur_dir:newstep += 1while 0 <= new_pos[0] < n and 0 <= new_pos[1] < n and vis.get(new_pos, 0) == 0:vis[new_pos] = 1  q.put(new_pos + (newstep, dir))new_pos = (new_pos[0] + dir[0], new_pos[1] + dir[1])return ans - 1 if ans!= -1 else ansn = int(input())
board = [list(input().split()) for _ in range(n)]
start = None
end = None
for i in range(n):for j in range(n):if board[i][j] == 'A':start = (i, j)elif board[i][j] == 'B':end = (i, j)
result = find_min_turns(n, start, end, board)
print(result)

方案二

上述的方法虽然过了这个题目，但是我手搓了一个样例他没有过

7
x x x x x x x
x x . A x x x
x x . . . x x
x x . . x x x
x x . x x x x
x x . B x x x
x x x x x x x

对于这个样例用bfs就存在问题，他不是
左$\to$下$\to$右，
而是下$\to$左$\to$下$\to$右
这样一来就不符合题意了，因为没有找到最小的转弯次数的路线。

代码

C++

#include <bits/stdc++.h>
using namespace std;int n, x0, y0, xn, yn, ans = 0x7fffffff / 2, bj;
char l;
int a[105][105];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};void Read()
{scanf("%d", &n);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){cin >> l;if (l == 'A')x0 = i, y0 = j, a[i][j] = -1;if (l == 'B')xn = i, yn = j, a[i][j] = 0;if (l == 'x')a[i][j] = -1;}
}void dfs(int x, int y, int t, int k)
{if (k >= ans)return;if (x == xn && y == yn){ans = min(ans, k);bj = 1;return;}for (int i = 0; i < 4; i++){int nx = dx[i] + x;int ny = dy[i] + y;if (nx <= 0 || nx > n || ny <= 0 || ny > n)continue;if (!a[nx][ny]){a[nx][ny] = -1;int f = 0;if (i != t)f = 1;if (t == -1)f = 0;dfs(nx, ny, i, k + f);a[nx][ny] = 0;}}
}int main()
{Read();dfs(x0, y0, -1, 0);if (bj)printf("%d", ans);elseprintf("-1");return 0;
}

Python

def find_min_turns(matrix, start, end, n):directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]  # 右 下 左 上，分别对应方向索引0、1、2、3ans = float('inf')  # 初始化最少转弯次数为正无穷，后续取最小值来更新bj = False  # 标记是否找到终点def dfs(x, y, prev_direction, turn_count):nonlocal ans, bjif turn_count >= ans:# 如果当前转弯次数已经大于等于已知的最少转弯次数，直接返回，进行剪枝returnif (x, y) == end:# 如果到达终点，更新最少转弯次数，并标记已找到终点ans = min(ans, turn_count)bj = Truereturnfor i in range(4):new_x, new_y = x + directions[i][0], y + directions[i][1]if not (0 <= new_x < n and 0 <= new_y < n):# 判断新位置是否在棋盘范围内，如果超出范围则跳过该方向continueif matrix[new_x][new_y]!= 'x':# 如果新位置不是障碍物，则可以尝试往这个方向移动original_value = matrix[new_x][new_y]matrix[new_x][new_y] = 'x'  # 暂时标记为已访问（等同于障碍物），避免重复访问# 判断是否转弯，根据当前方向和上一步方向是否不同来确定additional_turn = 1 if i!= prev_direction and prev_direction!= -1 else 0dfs(new_x, new_y, i, turn_count + additional_turn)matrix[new_x][new_y] = original_value  # 回溯，恢复该位置原来的值dfs(start[0], start[1], -1, 0)return ans if bj else -1n = int(input())
matrix = [input().split() for _ in range(n)]
for i in range(n):for j in range(n):if matrix[i][j] == 'A':start = (i, j)elif matrix[i][j] == 'B':end = (i, j)
result = find_min_turns(matrix, start, end, n)
print(result)

一、主要变量说明

1. 主要变量：
   • directions：一个包含四个元组的列表，[(1, 0), (0, -1), (-1, 0), (0, 1)]，分别对应向右、向下、向左、向上四个方向上坐标的变化量，用于在棋盘上计算移动后的新位置。例如，(1, 0)表示在x（行）方向增加1，y（列）方向不变，即向右移动一格。
   • ans：初始化为正无穷大（float('inf')），用于记录在搜索过程中发现的从起点到终点的最少转弯次数，后续会不断更新取最小值。
   • bj：布尔类型变量，初始化为False，用于标记是否已经找到终点，当找到终点后将其置为True。

三、核心算法逻辑（dfs函数部分）

dfs函数是基于深度优先搜索（DFS）的递归函数，用于遍历从起点开始的所有可能路径，并计算转弯次数，其详细逻辑如下：

1. 剪枝操作（提前返回情况）：
   在dfs函数开头，有如下判断语句：

if turn_count >= ans:return

这是一种剪枝操作，如果当前路径已经走过的转弯次数（turn_count）大于等于已经记录的最少转弯次数（ans），那么就没必要再继续沿着这条路径探索下去了，直接返回，避免不必要的计算，提高搜索效率。

2. 到达终点情况判断：

if (x, y) == end:ans = min(ans, turn_count)bj = Truereturn

当当前位置（(x, y)）与终点坐标（end）相等时，说明找到了一条从起点到终点的路径。此时，更新最少转弯次数（取当前记录的最少转弯次数和这条路径的转弯次数中的较小值），并将bj标记置为True表示已经找到终点，然后返回结束当前递归分支的探索。

3. 遍历四个方向探索新位置：
   通过以下循环遍历四个方向：

for i in range(4):new_x, new_y = x + directions[i][0], y + directions[i][1]if not (0 <= new_x < n and 0 <= new_y < n):continueif matrix[new_x][new_y]!= 'x':...

• 首先，根据directions数组中定义的方向变化量，计算在当前位置（(x, y)）向第i个方向移动后的新位置坐标（new_x，new_y）。
• 接着，判断新位置是否在棋盘范围内（通过判断行列索引是否满足0 <= new_x < n和0 <= new_y < n），如果超出范围则跳过该方向，继续尝试下一个方向。
• 如果新位置不是障碍物（即matrix[new_x][new_y]!= 'x'），则可以尝试往这个方向移动。

4. 标记、转弯判断及递归调用：
   当确定可以往某个方向移动时，执行以下操作：

original_value = matrix[new_x][new_y]
matrix[new_x][new_y] = 'x'
additional_turn = 1 if i!= prev_direction and prev_direction!= -1 else 0
dfs(new_x, new_y, i, turn_count + additional_turn)
matrix[new_x][new_y] = original_value

• 先保存新位置原本的值（通过original_value变量），然后将新位置标记为'x'（等同于设置为障碍物），这样做是为了避免在同一次搜索中重复访问该位置，防止陷入死循环。
• 通过判断当前方向（i）和上一步的方向（prev_direction）是否不同（并且上一步方向不是初始的-1情况）来确定是否需要转弯，如果不同则转弯次数加1（additional_turn为1），否则不加（additional_turn为0）。
• 接着，以新位置（new_x，new_y）、当前方向（i）以及更新后的转弯次数（turn_count + additional_turn）为参数，递归调用dfs函数，继续探索从新位置出发的路径情况。
• 最后，在递归调用结束后（无论是否找到终点或者探索完该分支），通过matrix[new_x][new_y] = original_value语句将新位置恢复为原来的值，进行回溯操作，以便后续其他路径探索时该位置能正常被访问。

四、主程序部分

1. 输入棋盘大小及构建棋盘矩阵：

n = int(input())
matrix = [input().split() for _ in range(n)]

首先通过input()函数获取用户输入的棋盘边长n，然后通过列表推导式构建二维的棋盘矩阵matrix，每一行的元素通过split()方法对输入的字符串进行分割得到（假设输入的每行字符串是以空格等分隔符隔开的字符元素）。

2. 寻找起点和终点坐标：

for i in range(n):for j in range(n):if matrix[i][j] == 'A':start = (i, j)elif matrix[i][j] == 'B':end = (i, j)

通过两层嵌套的循环遍历整个棋盘矩阵，找到标记为'A'的起点坐标赋值给start变量，找到标记为'B'的终点坐标赋值给end变量。

3. 调用函数并输出结果：

result = find_min_turns(matrix, start, end, n)
print(result)

最后，调用find_min_turns函数传入构建好的棋盘矩阵、起点坐标、终点坐标以及棋盘边长参数，获取从起点到终点的最少转弯次数结果，并将结果打印输出。如果无法到达终点，函数会按照逻辑返回-1并输出。