题目描述
某长方形停车场,每个车位上方都有对应监控器,当且仅当在当前车位或者前后左右四个方向任意一个车位范围停车时,监控器才需要打开;
给出某一时刻停车场的停车分布,请统计最少需要打开多少个监控器;
输入描述
第一行输入m,n表示长宽,满足1 < m,n <= 20;
后面输入m行,每行有n个0或1的整数,整数间使用一个空格隔开,表示该行已停车情况,其中0表示空位,1表示已停;
输出描述
最少需要打开监控器的数量;
用例
输入 | 3 3 0 0 0 0 1 0 0 0 0 |
输出 | 5 |
说明 | 无 |
题目解析
本题题意比较难以理解,但是画一幅图给大家看下就懂了
停车(1)的位置必须要打开监控器,另外停车位置的上下左右位置(1或0)的监控器也要打开,问最终需要打开多少个监控器?
即,求解上面图示种有颜色的格子数量。
解题思路如下:文章来源:https://www.toymoban.com/news/detail-511335.html
遍历矩阵每一个元素,文章来源地址https://www.toymoban.com/news/detail-511335.html
- 如果元素值为1,对应位置的监控器就要打开。
- 如果元素值为0,则需要进一步检查其上下左右四个位置,只要这四个位置有一个元素值为1,则当前位置的监控器需要打开
JavaScript算法源码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
const [m, n] = (await readline()).split(" ").map(Number);
const matrix = [];
for (let i = 0; i < m; i++) {
matrix.push((await readline()).split(" ").map(Number));
}
console.log(getResult(matrix, m, n));
})();
function getResult(matrix, m, n) {
// 记录需要打开的监控器数量
let count = 0;
// 上下左右四个方向的偏移量
const offsets = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
];
for (let x = 0; x < m; x++) {
for (let y = 0; y < n; y++) {
// 如果元素值为1,对应位置的监控器就要打开
if (matrix[x][y] === 1) {
count++;
continue;
}
// 如果元素值为0,则需要进一步检查其上下左右4个位置,只要这四个位置有一个元素值为1,则当前位置的监控器需要打开
for (let [offsetX, offsetY] of offsets) {
const newX = x + offsetX;
const newY = y + offsetY;
if (
newX >= 0 &&
newX < m &&
newY >= 0 &&
newY < n &&
matrix[newX][newY] === 1
) {
count++;
break;
}
}
}
}
return count;
}
Java算法源码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
System.out.println(getResult(m, n, matrix));
}
public static int getResult(int m, int n, int[][] matrix) {
// 记录需要打开的监控器数量
int count = 0;
// 上下左右四个方向的偏移量
int[][] offsets = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
// 如果元素值为1,对应位置的监控器就要打开
if (matrix[x][y] == 1) {
count++;
continue;
}
// 如果元素值为0,则需要进一步检查其上下左右4个位置,只要这四个位置有一个元素值为1,则当前位置的监控器需要打开
for (int[] offset : offsets) {
int newX = x + offset[0];
int newY = y + offset[1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 1) {
count++;
break;
}
}
}
}
return count;
}
}
Python算法源码
# 输入获取
m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(m)]
# 算法入口
def getResult():
# 记录需要打开的监控器数量
count = 0
# 上下左右四个方向的偏移量
offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))
for x in range(m):
for y in range(n):
# 如果元素值为1,对应位置的监控器就要打开
if matrix[x][y] == 1:
count += 1
continue
# 如果元素值为0,则需要进一步检查其上下左右4个位置,只要这四个位置有一个元素值为1,则当前位置的监控器需要打开
for offsetX, offsetY in offsets:
newX = x + offsetX
newY = y + offsetY
if m > newX >= 0 and n > newY >= 0 and matrix[newX][newY] == 1:
count += 1
break
return count
# 算法调用
print(getResult())
C算法源码
#include <stdio.h>
#define MAX_ROWS 20
#define MAX_COLS 20
int main()
{
// 输入获取
int m, n;
scanf("%d %d", &m, &n);
int matrix[MAX_ROWS][MAX_COLS];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &matrix[i][j]);
}
}
// 记录需要打开的监控器数量
int count = 0;
// 上下左右四个方向的偏移量
int offsets[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(int x = 0; x < m; x++) {
for(int y = 0; y < n; y++) {
// 如果元素值为1,对应位置的监控器就要打开
if(matrix[x][y] == 1) {
count++;
continue;
}
// 如果元素值为0,则需要进一步检查其上下左右4个位置,只要这四个位置有一个元素值为1,则当前位置的监控器需要打开
for(int i = 0; i < 4; i++) {
int offsetX = offsets[i][0];
int offsetY = offsets[i][1];
int newX = x + offsetX;
int newY = y + offsetY;
if(newX >=0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 1) {
count++;
break;
}
}
}
}
// 输出打印
printf("%d\n", count);
return 0;
}
到了这里,关于华为OD机试 - 需要打开多少监控器(Java & JS & Python)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!