【Python刷题】最少拐弯路线问题
题目描述
洛谷P1649
一、题目理解
首先，我们来看一下这道题目的要求。题目给定了一个 N×N（1≤N≤100） 的方格，方格中的每个格子有不同的状态，用 . 表示可以行走的格子，x 表示不能行走的格子，并且有起始点 A 和终点 B。我们要控制一个角色（比如题中的卡门或者贝西）从 A 点走到 B 点，这个角色因为自身特点不好转弯，只能沿着方格的边平行移动（也就是上下左右四个方向），然后求出从 A 到 B 最少要转 90 度弯的次数。如果无法到达终点，那就输出 -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
- 队列初始化及起始点入队：
创建一个队列q（这里使用 Python 的queue.Queue），然后把起始点相关的信息放入队列。起始点信息包含起始位置坐标（也就是start，它是一个二元组，比如(i, j)形式表示在方格中的位置），还有当前转弯次数（初始化为0）以及当前的方向（初始化为None，因为刚开始出发方向还不确定），整体就是start + (0, None)这样的形式放入队列q中，同时把起始点在vis字典中标记为已访问（vis[start] = 1）。 - 循环进行搜索：
只要队列q不为空，就持续进行循环搜索。每次从队列中取出一个元素，这个元素包含当前位置、转弯次数以及当前方向等信息，我们记为now，从中提取出当前位置cur_pos和当前方向cur_dir。 - 判断是否到达终点：
如果当前位置cur_pos就是终点end，那就意味着找到了一条从起点到终点的路径，把当前的转弯次数记录下来（也就是now[2]）作为答案，然后跳出循环。 - 探索相邻位置：
如果还没到达终点，那就遍历所有可能的移动方向（也就是前面定义的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 queue
def 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)] = 1
else:
vis[(i, j)] = 0
move = [(1, 0), (0, -1), (-1, 0), (0, 1)]
q = queue.Queue()
q.put(start + (0, None))
vis[start] = 1
ans = -1
while not q.empty():
now = q.get()
cur_pos = now[:2]
if cur_pos == end:
ans = now[2]
break
else:
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 += 1
while 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 ans
n = 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就存在问题，他不是
左
→
\rightarrow
→下
→
\rightarrow
→右，
而是下
→
\rightarrow
→左
→
\rightarrow
→下
→
\rightarrow
→右
这样一来就不符合题意了，因为没有找到最小的转弯次数的路线。
代码
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);
else
printf("-1");
return 0;
}
Python
def find_min_turns(matrix, start, end, n):
directions = [(1, 0), (0, -1), (-1, 0), (0, 1)] # 右 下 左 上，分别对应方向索引0、1、2、3
ans = float('inf') # 初始化最少转弯次数为正无穷，后续取最小值来更新
bj = False # 标记是否找到终点
def dfs(x, y, prev_direction, turn_count):
nonlocal ans, bj
if turn_count >= ans:
# 如果当前转弯次数已经大于等于已知的最少转弯次数，直接返回，进行剪枝
return
if (x, y) == end:
# 如果到达终点，更新最少转弯次数，并标记已找到终点
ans = min(ans, turn_count)
bj = True
return
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):
# 判断新位置是否在棋盘范围内，如果超出范围则跳过该方向
continue
if 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 0
dfs(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 -1
n = 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)
一、主要变量说明
- 主要变量：
directions：一个包含四个元组的列表，[(1, 0), (0, -1), (-1, 0), (0, 1)]，分别对应向右、向下、向左、向上四个方向上坐标的变化量，用于在棋盘上计算移动后的新位置。例如，(1, 0)表示在x（行）方向增加1，y（列）方向不变，即向右移动一格。ans：初始化为正无穷大（float('inf')），用于记录在搜索过程中发现的从起点到终点的最少转弯次数，后续会不断更新取最小值。bj：布尔类型变量，初始化为False，用于标记是否已经找到终点，当找到终点后将其置为True。
三、核心算法逻辑（dfs函数部分）
dfs函数是基于深度优先搜索（DFS）的递归函数，用于遍历从起点开始的所有可能路径，并计算转弯次数，其详细逻辑如下：
- 剪枝操作（提前返回情况）：
在dfs函数开头，有如下判断语句：
if turn_count >= ans:
return
这是一种剪枝操作，如果当前路径已经走过的转弯次数（turn_count）大于等于已经记录的最少转弯次数（ans），那么就没必要再继续沿着这条路径探索下去了，直接返回，避免不必要的计算，提高搜索效率。
- 到达终点情况判断：
if (x, y) == end:
ans = min(ans, turn_count)
bj = True
return
当当前位置（(x, y)）与终点坐标（end）相等时，说明找到了一条从起点到终点的路径。此时，更新最少转弯次数（取当前记录的最少转弯次数和这条路径的转弯次数中的较小值），并将bj标记置为True表示已经找到终点，然后返回结束当前递归分支的探索。
- 遍历四个方向探索新位置：
通过以下循环遍历四个方向：
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):
continue
if 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'），则可以尝试往这个方向移动。
- 标记、转弯判断及递归调用：
当确定可以往某个方向移动时，执行以下操作：
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语句将新位置恢复为原来的值，进行回溯操作，以便后续其他路径探索时该位置能正常被访问。
四、主程序部分
- 输入棋盘大小及构建棋盘矩阵：
n = int(input())
matrix = [input().split() for _ in range(n)]
首先通过input()函数获取用户输入的棋盘边长n，然后通过列表推导式构建二维的棋盘矩阵matrix，每一行的元素通过split()方法对输入的字符串进行分割得到（假设输入的每行字符串是以空格等分隔符隔开的字符元素）。
- 寻找起点和终点坐标：
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变量。
- 调用函数并输出结果：
result = find_min_turns(matrix, start, end, n)
print(result)
最后，调用find_min_turns函数传入构建好的棋盘矩阵、起点坐标、终点坐标以及棋盘边长参数，获取从起点到终点的最少转弯次数结果，并将结果打印输出。如果无法到达终点，函数会按照逻辑返回-1并输出。