💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🚔无人机巡逻路径

问题描述

LYA 公司正在开发一款用于巡逻的无人机。这款无人机被部署在一个矩形区域内，该区域由 个方格组成。每个方格要么是空地（用 表示），要么是障碍物（用 表示）。无人机从左上角（即坐标 ）出发，初始朝向右侧。

无人机的飞行规则如下：

1. 沿当前方向直线飞行，直到遇到边界或障碍物。
2. 遇到边界或障碍物时，顺时针旋转 度。
3. 重复步骤 1 和 2，直到无法继续飞行。

无人机经过的每个方格（包括起始位置）都被视为已巡逻。请计算无人机能够巡逻到的方格数量。

输入格式

第一行包含两个整数 和 ，表示矩形区域的行数和列数。

接下来 行，每行包含 个整数（ 或 ），描述了整个区域的布局。其中 表示空地， 表示障碍物。

输出格式

输出一个整数，表示无人机能够巡逻到的方格数量。

样例输入1

3 3
0 0 0
1 1 0
0 0 0

样例输出1

7

样例输入2

3 3
0 0 0
0 0 0
0 0 0

样例输出2

8

数据范围

• 
• 输入保证左上角 位置始终为空地（）

题解

本题可以通过 DFS 来模拟无人机的巡逻路径。

从起点开始，按照题目规则移动无人机，并记录已访问的格子。

关键点在于处理方向变化和避免无限循环，具体看代码实现。

对于每个格子最多被访问 4 次（每个方向一次），超过则说明进入循环，应当停止搜索。

时间复杂度为 ，空间复杂度也为 。

参考代码

• Python

# 定义方向数组，分别表示上、右、下、左四个方向
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def patrol_area(grid):
    m, n = len(grid), len(grid[0])
    visited = [[0] * n for _ in range(m)]
    patrolled = 0

    def dfs(x, y, direction):
        nonlocal patrolled
        # 如果当前格子访问次数超过4次，停止搜索
        if visited[x][y] >= 4:
            return
        # 如果是第一次访问该格子，增加巡逻计数
        if visited[x][y] == 0:
            patrolled += 1
        visited[x][y] += 1

        # 尝试四个方向
        for i in range(4):
            new_dir = (direction + i) % 4
            nx, ny = x + dx[new_dir], y + dy[new_dir]
            # 如果新位置有效且为空地，继续搜索
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:
                dfs(nx, ny, new_dir)
                return

    # 从左上角开始，初始方向向右
    dfs(0, 0, 1)
    return patrolled

# 读取输入
m, n = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(m)]

# 计算并输出结果
result = patrol_area(grid)
print(