【Python刷题】最少拐弯路线问题

🕗 发布于 2024-11-18 21:12 python 开发语言 算法 bfs

在这里插入图片描述

题目描述

一、题目理解

首先，我们来看一下这道题目的要求。题目给定了一个 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并输出。

原文地址：https://blog.csdn.net/qq_59306099/article/details/143833432

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：简单实现QT对象的[json]序列化与反序列化
下一篇：网络

二维费用背包问题
还是分为选和不选第 i 个元素，如果不选就是继承上一个状态 dp[i - 1][j][k]，如果选，由于总人数不能超过 j ，是需要 j >= g[i] 的，也就是 j - g[i] 不能小于
阅读更多2024-11-19
LeetCode17：电话号码的字母组合
这个题目也就是先使用一个映射定义好字符与数字的映射关系，然后再根据回溯三部曲来去写这个题目。
阅读更多2024-11-19
TypeScript中泛型的详细介绍
在TypeScript（TS）中，泛型（Generics）是一种强大的特性，它允许在定义函数、接口或类时不预先指定具体的类型，而是在使用的时候再指定类型。这种参数化类型的方式使得代码更加灵活和可复用。
阅读更多2024-11-19
String类型
regionMatches` 是 Java 中 `String` 类的一个方法，它用于比较两个字符串在指定区域内的子串是否相等。类的行为都是非法的。- 返回值：一个整数，表示调用该方法
阅读更多2024-11-19
大模型呼叫中心，如何建设坐席辅助系统？
综上所述，建设大模型呼叫中心坐席辅助系统需要综合考虑多个方面，从需求分析和设计到系统上线运行和优化升级，每个步骤都至关重要。通过选择合适的系统解决方案、配置高性能的硬件设备、集成先进的软件系统以及持续
阅读更多2024-11-19
《生成式 AI》课程第4講：訓練不了人工智慧？你可以訓練你自己 (中)
这一系列的作业是为 2024 年春季的《生成式 AI》课程设计的，共包含十个作业。每个作业都对应一个具体的主题，例如真假难辨的世界、AI 应用开发、AI催眠大师、LLM 微调等。承接上一讲：《生成式
阅读更多2024-11-19
【C++】哈希表的实现详解
在顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率决于搜
阅读更多2024-11-19
Leetcode 有效的数独
这段代码解决的是的问题，其算法思想是基于。falsetrue。
阅读更多2024-11-19
小林Coding—Java「五、Java虚拟机面试篇」
小林Coding—Java「五、Java虚拟机面试篇」笔记整理
阅读更多2024-11-19
一个简单的图像分类项目（九）并行训练的学习：多GPU的DP（DataParallel数据并行）
将电脑装成Ubuntu、Windows双系统，并在Ubuntu上继续学习。在现代深度学习中，多主机多GPU训练已经变得非常常见，尤其是对于大规模模型和数据集。最简单和早期的并行计算比如NVIDIA的S
阅读更多2024-11-19