华为OD机试 - 需要打开多少监控器（Python/JS/C/C++ 2024 E卷 100分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

二、输入描述

第一行输入 m，n 表示长宽，满足 1 < m, n <= 20；

后面输入 m 行，每行有 n 个 0 或 1 的整数，整数间使用一个空格隔开，表示该行停车情况，其中 0 表示空位，1 表示已停。

三、输出描述

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

四、测试用例

测试用例1

1、输入

3 3
0 0 0
0 1 0
0 0 0

2、输出

测试用例2

1、输入

3 3
1 0 0
0 1 0
0 0 0

2、输出

五、解题思路

对于每一个车位，检查其自身和四个相邻方向的车位是否有车辆停放（即是否有 1）。

如果满足条件，则计数该监控器需要开启。

在检查相邻车位时，需要确保不超出矩阵的边界，以避免数组越界错误。

六、Python算法源码

def count_cameras(m, n, parking_lot):"""统计最少需要开启的监控器数量。:param m: 矩阵的行数:param n: 矩阵的列数:param parking_lot: 停车场的二维列表，0表示空位，1表示已停车辆:return: 最少需要开启的监控器数量"""# 定义四个方向：上、下、左、右directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]camera_count = 0  # 初始化监控器开启数量for i in range(m):for j in range(n):# 检查当前车位或四个相邻方向是否有车辆停放if parking_lot[i][j] == 1:camera_count += 1  # 当前车位有车辆，监控器需要开启else:# 检查四个相邻方向for dx, dy in directions:ni, nj = i + dx, j + dy  # 相邻车位的坐标if 0 <= ni < m and 0 <= nj < n:if parking_lot[ni][nj] == 1:camera_count += 1  # 相邻车位有车辆，监控器需要开启break  # 只需满足一个方向即可，不需继续检查return camera_countdef main():import sys# 读取所有输入lines = sys.stdin.read().strip().split('\n')if len(lines) < 1:print("-1")return# 读取第一行，解析m和nfirst_line = lines[0].strip()try:m, n = map(int, first_line.split())except:print("-1")return# 验证m和n的范围if not (1 < m <= 20) or not (1 < n <= 20):print("-1")return# 检查是否有足够的停车分布行if len(lines) != m + 1:print("-1")returnparking_lot = []for i in range(1, m + 1):try:row = list(map(int, lines[i].strip().split()))if len(row) != n:print("-1")return# 验证每个车位的值for val in row:if val not in [0, 1]:print("-1")returnparking_lot.append(row)except:print("-1")return# 计算最少需要开启的监控器数量result = count_cameras(m, n, parking_lot)print(result)if __name__ == "__main__":main()

七、JavaScript算法源码

function countCameras(m, n, parkingLot) {/*** 统计最少需要开启的监控器数量。* @param {number} m - 矩阵的行数* @param {number} n - 矩阵的列数* @param {number[][]} parkingLot - 停车场的二维数组，0表示空位，1表示已停车辆* @returns {number} 最少需要开启的监控器数量*/// 定义四个方向：上、下、左、右const directions = [[-1, 0], // 上[1, 0],  // 下[0, -1], // 左[0, 1]   // 右];let cameraCount = 0; // 初始化监控器开启数量for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (parkingLot[i][j] === 1) {cameraCount += 1; // 当前车位有车辆，监控器需要开启} else {// 检查四个相邻方向for (let [dx, dy] of directions) {const ni = i + dx;const nj = j + dy;// 确保相邻车位在矩阵范围内if (ni >= 0 && ni < m && nj >= 0 && nj < n) {if (parkingLot[ni][nj] === 1) {cameraCount += 1; // 相邻车位有车辆，监控器需要开启break; // 只需满足一个方向即可，跳出循环}}}}}}return cameraCount; // 返回监控器开启数量
}function main() {const fs = require('fs'); // 引入文件系统模块const input = fs.readFileSync('/dev/stdin', 'utf8'); // 读取标准输入const lines = input.trim().split('\n'); // 按行分割输入if (lines.length < 1) {console.log("-1");return;}// 读取第一行，解析m和nconst firstLine = lines[0].trim();const mn = firstLine.split(' ');if (mn.length !== 2) { // 确保有两个数字console.log("-1");return;}const m = parseInt(mn[0]);const n = parseInt(mn[1]);// 验证m和n的范围if (isNaN(m) || isNaN(n) || m <= 1 || m > 20 || n <=1 || n >20) {console.log("-1");return;}// 检查是否有足够的停车分布行if (lines.length !== m +1) {console.log("-1");return;}const parkingLot = [];for (let i =1; i <= m; i++) {const rowStr = lines[i].trim();const row = rowStr.split(' ').map(Number);if (row.length !== n) { // 每行必须有n个分数console.log("-1");return;}// 验证每个车位的值for (let val of row) {if (val !==0 && val !==1) {console.log("-1");return;}}parkingLot.push(row);}// 计算最少需要开启的监控器数量const result = countCameras(m, n, parkingLot);console.log(result);
}// 执行主函数
main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>// 定义方向数组，表示上、下、左、右
int directions[4][2] = {{-1, 0}, // 上{1, 0},  // 下{0, -1}, // 左{0, 1}   // 右
};int main() {int m, n;// 读取第一行，获取m和nif (scanf("%d %d", &m, &n) != 2) {printf("-1\n");return 0;}// 验证m和n的范围if (m <= 1 || m > 20 || n <=1 || n >20) {printf("-1\n");return 0;}// 动态分配二维数组int parking_lot[m][n];// 读取停车分布for (int i =0; i < m; i++) {for (int j =0; j < n; j++) {if (scanf("%d", &parking_lot[i][j]) !=1) {printf("-1\n");return 0;}// 验证车位值if (parking_lot[i][j] !=0 && parking_lot[i][j] !=1) {printf("-1\n");return 0;}}}int camera_count =0; // 初始化监控器开启数量// 遍历每个车位for (int i =0; i < m; i++) {for (int j =0; j < n; j++) {if (parking_lot[i][j] ==1) {camera_count +=1; // 当前车位有车辆，监控器需要开启}else {// 检查四个相邻方向for (int d =0; d <4; d++) {int ni = i + directions[d][0];int nj = j + directions[d][1];// 确保相邻车位在矩阵范围内if (ni >=0 && ni < m && nj >=0 && nj < n) {if (parking_lot[ni][nj] ==1) {camera_count +=1; // 相邻车位有车辆，监控器需要开启break; // 只需满足一个方向即可，跳出循环}}}}}}// 输出监控器开启数量printf("%d\n", camera_count);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
using namespace std;// 定义方向数组，表示上、下、左、右
const int directions[4][2] = {{-1, 0}, // 上{1, 0},  // 下{0, -1}, // 左{0, 1}   // 右
};int main(){ios::sync_with_stdio(false); // 关闭同步，提高IO效率cin.tie(0); // 取消cin的绑定int m, n;// 读取第一行，获取m和nif(!(cin >> m >> n)){cout << "-1\n";return 0;}// 验证m和n的范围if(m <=1 || m >20 || n <=1 || n >20){cout << "-1\n";return 0;}// 初始化停车场二维向量vector<vector<int>> parking_lot(m, vector<int>(n, 0));// 读取停车分布for(int i =0; i <m; i++){for(int j =0; j <n; j++){if(!(cin >> parking_lot[i][j])){cout << "-1\n";return 0;}// 验证车位值if(parking_lot[i][j] !=0 && parking_lot[i][j] !=1){cout << "-1\n";return 0;}}}int camera_count =0; // 初始化监控器开启数量// 遍历每个车位for(int i =0; i <m; i++){for(int j =0; j <n; j++){if(parking_lot[i][j] ==1){camera_count +=1; // 当前车位有车辆，监控器需要开启}else{// 检查四个相邻方向for(int d =0; d <4; d++){int ni = i + directions[d][0];int nj = j + directions[d][1];// 确保相邻车位在矩阵范围内if(ni >=0 && ni <m && nj >=0 && nj <n){if(parking_lot[ni][nj] ==1){camera_count +=1; // 相邻车位有车辆，监控器需要开启break; // 只需满足一个方向即可，跳出循环}}}}}}// 输出监控器开启数量cout << camera_count << "\n";return 0;
}