1. 华为OD机考双机位C卷解析机器人活动区域Java实现最近在准备华为OD机考的朋友们应该都注意到了C卷中出现的机器人活动区域题目这道题结合了矩阵遍历和动态规划的思想是典型的算法应用题。作为经历过三次华为OD机考的老兵我想分享一下这道题的解题思路和Java实现方案特别针对双机位考试环境下的注意事项。双机位机考意味着除了主摄像头外侧面还会有一个监控机位这对代码编写和调试提出了更高要求。我们需要在保证算法正确性的前提下写出清晰易读的代码结构。下面我将从题目分析、解题思路到完整实现一步步拆解这个高频考题。1.1 题目核心需求题目给定一个m×n的矩阵网格其中某些格子是障碍物用1表示其余是可通行的空地用0表示。机器人从左上角(0,0)出发每次只能向右或向下移动要求计算机器人能够到达的活动区域大小。关键约束条件网格大小不超过100×100时间复杂度需控制在O(mn)以内空间复杂度优化是加分项1.2 输入输出示例示例输入[ [0,0,0], [0,1,0], [0,0,0] ]预期输出5解释机器人可以到达除(1,1)外的所有格子共5个可到达区域。2. 解题思路与算法选择2.1 基础解法DFS/BFS遍历最直观的解法是使用深度优先搜索(DFS)或广度优先搜索(BFS)来探索可达区域。这两种方法都能正确解决问题但在实际机考中各有优劣// DFS示例代码框架 public int uniquePathsWithObstacles(int[][] grid) { if(grid null || grid.length 0) return 0; int m grid.length, n grid[0].length; boolean[][] visited new boolean[m][n]; return dfs(grid, 0, 0, visited); } private int dfs(int[][] grid, int i, int j, boolean[][] visited) { if(i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 1 || visited[i][j]) { return 0; } visited[i][j] true; return 1 dfs(grid, i1, j, visited) dfs(grid, i, j1, visited); }DFS的优点是代码简洁但在最坏情况下如全0矩阵会因为递归深度导致栈溢出。BFS使用队列则没有这个问题但代码量稍大。2.2 优化解法动态规划更高效的解法是动态规划(DP)这也是面试官更期待看到的方案。DP思路是构建一个二维数组dp其中dp[i][j]表示到达(i,j)的路径数或可达性。状态转移方程dp[i][j] 0, if grid[i][j] 1 dp[i][j] dp[i-1][j] dp[i][j-1], otherwise边界条件dp[0][0] (grid[0][0] 0) ? 1 : 0第一行和第一列需要特殊处理2.3 空间优化技巧在机考环境中展示空间优化能力可以加分。观察发现dp[i][j]只依赖于上一行和当前行左边的值因此可以将空间复杂度从O(mn)降到O(n)public int uniquePathsWithObstacles(int[][] grid) { int n grid[0].length; int[] dp new int[n]; dp[0] grid[0][0] 0 ? 1 : 0; for(int[] row : grid) { for(int j 0; j n; j) { if(row[j] 1) { dp[j] 0; } else if(j 0) { dp[j] dp[j-1]; } } } return dp[n-1]; }3. 完整Java实现与双机位注意事项3.1 完整代码实现结合双机位考试的特殊要求我们需要写出既高效又易读的代码。以下是推荐实现public class RobotActivityArea { public int calculateActivityArea(int[][] grid) { if(grid null || grid.length 0 || grid[0].length 0) return 0; int m grid.length, n grid[0].length; int[][] dp new int[m][n]; // 初始化起点 dp[0][0] grid[0][0] 0 ? 1 : 0; if(dp[0][0] 0) return 0; // 起点就是障碍 // 初始化第一列 for(int i 1; i m; i) { dp[i][0] (grid[i][0] 0 dp[i-1][0] 1) ? 1 : 0; } // 初始化第一行 for(int j 1; j n; j) { dp[0][j] (grid[0][j] 0 dp[0][j-1] 1) ? 1 : 0; } // 动态规划填充 for(int i 1; i m; i) { for(int j 1; j n; j) { if(grid[i][j] 0) { dp[i][j] dp[i-1][j] dp[i][j-1]; } } } // 统计可达区域 int area 0; for(int i 0; i m; i) { for(int j 0; j n; j) { if(dp[i][j] 0) area; } } return area; } }3.2 双机位考试特别提示代码风格规范类名使用大驼峰方法名使用小驼峰添加必要的空行分隔逻辑块关键步骤添加简短注释但不要过度注释边界条件处理显式检查null和空数组单独处理起点就是障碍的情况第一行和第一列需要特殊初始化调试技巧在本地IDE准备好测试用例使用System.out打印中间结果时保持简洁遇到问题时先检查边界条件时间分配建议5分钟分析题目15分钟编写代码5分钟测试和调试剩余时间优化和添加注释4. 常见问题与调试技巧4.1 典型错误案例数组越界忘记检查i-1或j-1是否为负解决方案单独处理第一行和第一列障碍物处理不当遇到障碍物时没有将dp值设为0解决方案在动态规划循环开始前先判断grid[i][j]初始化错误第一行/列中某个位置是障碍物时后续位置都应不可达解决方案使用条件判断前一个位置是否可达4.2 测试用例设计完整的测试应该包含以下场景Test public void testCases() { RobotActivityArea solution new RobotActivityArea(); // 常规情况 int[][] grid1 {{0,0,0},{0,1,0},{0,0,0}}; assertEquals(5, solution.calculateActivityArea(grid1)); // 起点是障碍 int[][] grid2 {{1,0},{0,0}}; assertEquals(0, solution.calculateActivityArea(grid2)); // 全0矩阵 int[][] grid3 {{0,0},{0,0}}; assertEquals(4, solution.calculateActivityArea(grid3)); // 全1矩阵 int[][] grid4 {{1,1},{1,1}}; assertEquals(0, solution.calculateActivityArea(grid4)); // 单行单列 int[][] grid5 {{0,0,0}}; assertEquals(3, solution.calculateActivityArea(grid5)); }4.3 性能优化建议提前终止如果在初始化阶段发现终点不可达可以直接返回0这在大型矩阵中可以节省大量计算时间并行统计统计可达区域时可以与DP填充合并但这会降低代码可读性需权衡利弊位图优化对于特别大的矩阵可以用位运算优化空间但在机考中通常不需要这种级别的优化5. 华为OD机考准备建议5.1 高频考点梳理除了这类矩阵遍历问题华为OD机考C卷还常考字符串处理KMP、滑动窗口树形结构二叉树遍历、最近公共祖先图算法DFS、BFS、最短路径贪心算法和排序结合问题5.2 双机位环境适应环境配置提前熟悉在线编程界面准备代码片段模板如快速输入输出监控注意事项保持主摄像头对准面部和屏幕侧机位要能看到键盘和桌面避免频繁切换窗口或长时间停顿时间管理简单题控制在20分钟内中等难度题30-40分钟留出10分钟检查时间5.3 资源推荐在线练习平台LeetCode华为OD专题牛客网华为题库Codeforces动态规划专题书籍推荐《剑指Offer》动态规划章节《算法导论》图算法部分《编程之美》中的数学思维题视频资源B站上的华为OD机考经验分享YouTube上的动态规划教学慕课网的Java算法精讲在实际考试中遇到机器人活动区域这类题目时建议先花2-3分钟在白纸上画出状态转移表理清思路后再开始编码。双机位环境下清晰的解题思路展示有时比直接写代码更重要。
1. 华为OD机考双机位C卷解析机器人活动区域Java实现最近在准备华为OD机考的朋友们应该都注意到了C卷中出现的机器人活动区域题目这道题结合了矩阵遍历和动态规划的思想是典型的算法应用题。作为经历过三次华为OD机考的老兵我想分享一下这道题的解题思路和Java实现方案特别针对双机位考试环境下的注意事项。双机位机考意味着除了主摄像头外侧面还会有一个监控机位这对代码编写和调试提出了更高要求。我们需要在保证算法正确性的前提下写出清晰易读的代码结构。下面我将从题目分析、解题思路到完整实现一步步拆解这个高频考题。1.1 题目核心需求题目给定一个m×n的矩阵网格其中某些格子是障碍物用1表示其余是可通行的空地用0表示。机器人从左上角(0,0)出发每次只能向右或向下移动要求计算机器人能够到达的活动区域大小。关键约束条件网格大小不超过100×100时间复杂度需控制在O(mn)以内空间复杂度优化是加分项1.2 输入输出示例示例输入[ [0,0,0], [0,1,0], [0,0,0] ]预期输出5解释机器人可以到达除(1,1)外的所有格子共5个可到达区域。2. 解题思路与算法选择2.1 基础解法DFS/BFS遍历最直观的解法是使用深度优先搜索(DFS)或广度优先搜索(BFS)来探索可达区域。这两种方法都能正确解决问题但在实际机考中各有优劣// DFS示例代码框架 public int uniquePathsWithObstacles(int[][] grid) { if(grid null || grid.length 0) return 0; int m grid.length, n grid[0].length; boolean[][] visited new boolean[m][n]; return dfs(grid, 0, 0, visited); } private int dfs(int[][] grid, int i, int j, boolean[][] visited) { if(i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 1 || visited[i][j]) { return 0; } visited[i][j] true; return 1 dfs(grid, i1, j, visited) dfs(grid, i, j1, visited); }DFS的优点是代码简洁但在最坏情况下如全0矩阵会因为递归深度导致栈溢出。BFS使用队列则没有这个问题但代码量稍大。2.2 优化解法动态规划更高效的解法是动态规划(DP)这也是面试官更期待看到的方案。DP思路是构建一个二维数组dp其中dp[i][j]表示到达(i,j)的路径数或可达性。状态转移方程dp[i][j] 0, if grid[i][j] 1 dp[i][j] dp[i-1][j] dp[i][j-1], otherwise边界条件dp[0][0] (grid[0][0] 0) ? 1 : 0第一行和第一列需要特殊处理2.3 空间优化技巧在机考环境中展示空间优化能力可以加分。观察发现dp[i][j]只依赖于上一行和当前行左边的值因此可以将空间复杂度从O(mn)降到O(n)public int uniquePathsWithObstacles(int[][] grid) { int n grid[0].length; int[] dp new int[n]; dp[0] grid[0][0] 0 ? 1 : 0; for(int[] row : grid) { for(int j 0; j n; j) { if(row[j] 1) { dp[j] 0; } else if(j 0) { dp[j] dp[j-1]; } } } return dp[n-1]; }3. 完整Java实现与双机位注意事项3.1 完整代码实现结合双机位考试的特殊要求我们需要写出既高效又易读的代码。以下是推荐实现public class RobotActivityArea { public int calculateActivityArea(int[][] grid) { if(grid null || grid.length 0 || grid[0].length 0) return 0; int m grid.length, n grid[0].length; int[][] dp new int[m][n]; // 初始化起点 dp[0][0] grid[0][0] 0 ? 1 : 0; if(dp[0][0] 0) return 0; // 起点就是障碍 // 初始化第一列 for(int i 1; i m; i) { dp[i][0] (grid[i][0] 0 dp[i-1][0] 1) ? 1 : 0; } // 初始化第一行 for(int j 1; j n; j) { dp[0][j] (grid[0][j] 0 dp[0][j-1] 1) ? 1 : 0; } // 动态规划填充 for(int i 1; i m; i) { for(int j 1; j n; j) { if(grid[i][j] 0) { dp[i][j] dp[i-1][j] dp[i][j-1]; } } } // 统计可达区域 int area 0; for(int i 0; i m; i) { for(int j 0; j n; j) { if(dp[i][j] 0) area; } } return area; } }3.2 双机位考试特别提示代码风格规范类名使用大驼峰方法名使用小驼峰添加必要的空行分隔逻辑块关键步骤添加简短注释但不要过度注释边界条件处理显式检查null和空数组单独处理起点就是障碍的情况第一行和第一列需要特殊初始化调试技巧在本地IDE准备好测试用例使用System.out打印中间结果时保持简洁遇到问题时先检查边界条件时间分配建议5分钟分析题目15分钟编写代码5分钟测试和调试剩余时间优化和添加注释4. 常见问题与调试技巧4.1 典型错误案例数组越界忘记检查i-1或j-1是否为负解决方案单独处理第一行和第一列障碍物处理不当遇到障碍物时没有将dp值设为0解决方案在动态规划循环开始前先判断grid[i][j]初始化错误第一行/列中某个位置是障碍物时后续位置都应不可达解决方案使用条件判断前一个位置是否可达4.2 测试用例设计完整的测试应该包含以下场景Test public void testCases() { RobotActivityArea solution new RobotActivityArea(); // 常规情况 int[][] grid1 {{0,0,0},{0,1,0},{0,0,0}}; assertEquals(5, solution.calculateActivityArea(grid1)); // 起点是障碍 int[][] grid2 {{1,0},{0,0}}; assertEquals(0, solution.calculateActivityArea(grid2)); // 全0矩阵 int[][] grid3 {{0,0},{0,0}}; assertEquals(4, solution.calculateActivityArea(grid3)); // 全1矩阵 int[][] grid4 {{1,1},{1,1}}; assertEquals(0, solution.calculateActivityArea(grid4)); // 单行单列 int[][] grid5 {{0,0,0}}; assertEquals(3, solution.calculateActivityArea(grid5)); }4.3 性能优化建议提前终止如果在初始化阶段发现终点不可达可以直接返回0这在大型矩阵中可以节省大量计算时间并行统计统计可达区域时可以与DP填充合并但这会降低代码可读性需权衡利弊位图优化对于特别大的矩阵可以用位运算优化空间但在机考中通常不需要这种级别的优化5. 华为OD机考准备建议5.1 高频考点梳理除了这类矩阵遍历问题华为OD机考C卷还常考字符串处理KMP、滑动窗口树形结构二叉树遍历、最近公共祖先图算法DFS、BFS、最短路径贪心算法和排序结合问题5.2 双机位环境适应环境配置提前熟悉在线编程界面准备代码片段模板如快速输入输出监控注意事项保持主摄像头对准面部和屏幕侧机位要能看到键盘和桌面避免频繁切换窗口或长时间停顿时间管理简单题控制在20分钟内中等难度题30-40分钟留出10分钟检查时间5.3 资源推荐在线练习平台LeetCode华为OD专题牛客网华为题库Codeforces动态规划专题书籍推荐《剑指Offer》动态规划章节《算法导论》图算法部分《编程之美》中的数学思维题视频资源B站上的华为OD机考经验分享YouTube上的动态规划教学慕课网的Java算法精讲在实际考试中遇到机器人活动区域这类题目时建议先花2-3分钟在白纸上画出状态转移表理清思路后再开始编码。双机位环境下清晰的解题思路展示有时比直接写代码更重要。
