本人是算法小白,甚至也没有做过Leetcode。所以,我相信【同为菜鸡的我更能理解作为菜鸡的你们的痛点】。
OD,B 卷 100 分题目【OD 统一考试(B 卷)】
某长方形停车场每个车位上方都有一个监控器,只有当当前车位或者前后左右四个方向任意一个车位范围停有车时,监控器才需要打开。给定某一时刻停车场的停车分布,请统计最少需要打开多少个监控器。
第一行输入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
说实在,我刚看到题干的时候是有点懵的,有点读不清楚题目的意思。接着我看了【示例】的输入输出之后,更加懵逼了。就算看了答案,我还是不知所云。后面拿着题干去百度,再反复思考,才理清了其中缘由,哎,其实是我自己想复杂了(有点挫败)。
我自己反思了一下,为什么我会读不清楚题目意思:
大家抛开对停车场的固有印象,也不要去看上面那张鸟瞰图,就用最原始的【面向过程】的想法去看题目。通过读题干,我们可以得到以下条件:
1 < m, n <= 20
(那不就是一个二维数组嘛)m * n
个监控器)public class StatisticalMonitors {
/**
* m、n的范围。 1< m,n <= 20
*/
static final int MAX_COUNT = 20 + 1 + 1;
/**
* 【前、后、左、右】的坐标变化量
* 用来索引当前节点【前、后、左、右】的目标位置
*/
static final int AROUND[][] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
public static void main(String[] args) {
int row = 0, column = 0;
int[][] parkingLot = new int[MAX_COUNT][MAX_COUNT];
// 读入数据
Scanner scanner = new Scanner(System.in);
row = scanner.nextInt();
column = scanner.nextInt();
for (int r = 1; r <= row; r++) {
for (int c = 1; c <= column; c++) {
parkingLot[r][c] = scanner.nextInt();
}
}
// 统计数量
int monitorCount = 0;
for (int r = 1; r <= row; r++) {
for (int c = 1; c <= column; c++) {
// 当前节点有车,直接返回
int status = parkingLot[r][c];
if (status == 1) {
monitorCount++;
continue;
}
// 没车,看看四周
boolean b = checkAround(parkingLot, r, c);
if (b) {
monitorCount++;
}
}
}
System.out.println("停车场至少需要的监控数目:" + monitorCount);
}
/**
* 检查当前四周(前、后、左、右)有没有车停靠
*
* @return true-有车;false-没有车
*/
private static boolean checkAround(int[][] parkingLot, int curRow, int curColumn) {
for (int[] ints : AROUND) {
int newRow = curRow + ints[0];
int newColumn = curColumn + ints[1];
int status = parkingLot[newRow][newColumn];
if (status == 1) {
return true;
}
}
return false;
}
}
代码解读:
整体代码都很简单,我相信看我上面的代码估计也知道啥意思了。有一些需要特别声明的点:
AROUND
用来快速锚定当前位置的【前后左右】位置的坐标,并且为此改变了长宽条件变量MAX_COUNT
的值(20 -> 20 + 1 + 1
,下面我会解释为什么我要这么写)for
循环区间是[1, m]
而不是[0, m)
,这是为了方便索引(相当于把坐标整体往右下角移动了)。毕竟停车场边缘是坐标周围的坐标不好索引,需要做额外判断。这也是为什么,我要在MAX_COUNT = 20 + 1 + 1
的原因。其中,20
表示条件中说的长、宽范围;后面的1 + 1
表示的语义如下:
1
:整体往右下角移动1
:则是为了避免过多的安全判断。使当前节点周围节点可以索引。如果没有这个的话,那么在判断停车场边缘节点(即:数组边缘)的时候,为了防止数组越界,需要做额外的安全判断