成都网站建设交易,市场营销案例分析,龙岗建网站公司,贵州两学一做教育网站前言
本人是算法小白#xff0c;甚至也没有做过Leetcode。所以#xff0c;我相信【同为菜鸡的我更能理解作为菜鸡的你们的痛点】。
题干
OD#xff0c;B 卷 100 分题目【OD 统一考试#xff08;B 卷#xff09;】
1. 题目描述
某长方形停车场每个车位上方都有一个监控…前言
本人是算法小白甚至也没有做过Leetcode。所以我相信【同为菜鸡的我更能理解作为菜鸡的你们的痛点】。
题干
ODB 卷 100 分题目【OD 统一考试B 卷】
1. 题目描述
某长方形停车场每个车位上方都有一个监控器只有当当前车位或者前后左右四个方向任意一个车位范围停有车时监控器才需要打开。给定某一时刻停车场的停车分布请统计最少需要打开多少个监控器。
2. 输入描述 第一行输入m和n表示停车场的长和宽。满足条件1 m, n 20。 接下来的m行每行包含n个整数0或1表示该行停车位的情况。其中0表示空位1表示已停车。 3. 输出描述 输出最少需要打开的监控器数量 4. 示例
示例一 输入
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则是为了避免过多的安全判断。使当前节点周围节点可以索引。如果没有这个的话那么在判断停车场边缘节点即数组边缘的时候为了防止数组越界需要做额外的安全判断
