【模拟】2023B-统计监控

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P2503

题目描述

在一长方形停车场内，每个车位上方都有对应监控器，当且仅当在当前车位或者前后左右四个方向任意一个车位范围停车时，监控器才需要打开，给出某一时刻停车场的停车分布，请统计最少需要打开多少个监控器。

输入

第一行输入 m，n 表示长宽，满足 1 < m, n <= 20；后面输入 m 行，每行有 n 个 0 或 1 的整数，整数间使用一个空格隔开，表示该行已停车情况，其中 0表示空位，1 表示已停。

输出

最少需要打开监控器的数量。

示例一

输入

3 3
0 0 0
0 1 0
0 0 0

输出

5

示例二

输入

3 3
1 0 0
0 1 0
0 0 0

输出

6

解题思路

本题看似需要DFS或BFS进行，实则较为简单，直接依据题意模拟即可。

遍历二维矩阵，对于

• 0，如果其上下左右四个方向存在任意一个1，则该位置需要安装监控。
• 1，则该位置需要安装监控。

故直接遍历二维矩阵并且统计安装监控的数目即可。核心代码为

for i in range(m):
    for j in range(n):
        if grid[i][j] == 1:
            ans += 1
        else:
            for dx, dy in DERICTIONS:
                ni, nj = i+dx, j+dy
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                    ans += 1
                    break

代码

# 题目：2023B-统计监控
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟
# 代码看不懂的地方，请直接在群上提问


# 表示四个方向的数组
DERICTIONS = [(0,1), (1,0), (-1,0), (0,-1)]

m, n = map(int, input().split())
grid = list()
for _ in range(m):
    grid.append(list(map(int, input().split())))

ans = 0

# 遍历整个二维数组
for i in range(m):
    for j in range(n):
        # 遇到1，安装监控
        if grid[i][j] == 1:
            ans += 1
        # 遇到0，判断其上下左右是否存在1
        else:
            # 考虑上下左右四个方向
            for dx, dy in DERICTIONS:
                ni, nj = i+dx, j+dy
                # (ni, nj)未越界，且在grid中取值为1
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                    # (i,j)位置需要安装监控，同时可以退出循环
                    ans += 1
                    break

print(ans)

时空复杂度

时间复杂度：O(NM)。仅需遍历一次二维矩阵。

空间复杂度：O(1)。仅需若干常数变量。