题目
某长方形停车场,每个车位上方都有对应监控器,当且仅当在当前车位或者前后左右四个方向任意一个车位范围停车时,监控器才需要打开:
给出某一时刻停车场的停车分布,请统计最少需要打开多少个监控器
输入描述
第一行输入m,n表示长宽,满足1<m,n <= 20;
后面输入m行,每行有n个0或1的整数,整数间使用一个空格隔开,表示该行已停车情况,其中0表示空位,1表示已停:
输出描述
最少需要打开监控器的数量
示例1:
输入
3 3
0 0 0
0 1 0
0 0 0
输出
5
说明
中间1的位置上需要打开监视器,且其上下左右皆需要打开监视器,共5个。
思路
根据题意,就是找到是1或者临近单元格是1的单元格数量,直接遍历判断即可。
也可以理解为1的单元格,向周围扩散一次后,得到的1的单元格数量(类似宜居星球改造计划)
题解
java">package hwod;
import java.util.*;
//需要打开多少监视器
public class CalMonitorNum {
public static int[][] grids;
public static int m;
public static int n;
public static int[] x_dirs = new int[]{1, 0, -1, 0};
public static int[] y_dirs = new int[]{0, 1, 0, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
grids = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grids[i][j] = sc.nextInt();
}
}
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grids[i][j] == 1 || neighbor(i, j)) res++;
}
}
System.out.println(res);
}
private static boolean neighbor(int i, int j) {
for (int k = 0; k < 4; k++) {
int x = i + x_dirs[k], y = j + y_dirs[k];
if (x >= 0 && x < m && y >= 0 && y < n && grids[x][y] == 1) return true;
}
return false;
}
}