企业外贸网站推广,wordpress 汉化工具,站内seo是什么意思,网站建设专业课程文章目录 一、题目二、C# 题解 一、题目 设想有个机器人坐在一个网格的左上角#xff0c;网格 r 行 c 列。机器人只能向下或向右移动#xff0c;但不能走到一些被禁止的网格#xff08;有障碍物#xff09;。设计一种算法#xff0c;寻找机器人从左上角移动到右下角的路径… 文章目录 一、题目二、C# 题解 一、题目 设想有个机器人坐在一个网格的左上角网格 r 行 c 列。机器人只能向下或向右移动但不能走到一些被禁止的网格有障碍物。设计一种算法寻找机器人从左上角移动到右下角的路径。 网格中的障碍物和空位置分别用 1 和 0 来表示。 返回一条可行的路径路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径返回空数组。
示例 1: 输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: [[0,0],[0,1],[0,2],[1,2],[2,2]] 解释: 输入中标粗的位置即为输出表示的路径即 0行0列左上角 - 0行1列 - 0行2列 - 1行2列 - 2行2列右下角 说明r 和 c 的值均不超过 100。 点击此处跳转题目。
二、C# 题解 可以使用回溯解这里用动态规划好些。使用 path 记录当前位置是否能到达终点因此从终点开始向起点方向进行判断当前 path[i, j] 的值为 obstacleGrid[i][j] 0 (path[i 1, j] || path[i, j 1])即当前无障碍物且后方有可到达路径。对于边界情况需要优先特殊处理以免数组越界。
public class Solution {public IListIListint PathWithObstacles(int[][] obstacleGrid) {int r obstacleGrid.Length, c obstacleGrid[0].Length;IListIListint ans new ListIListint();bool[,] path new bool[r, c]; // 记录可到达路径if (obstacleGrid[r - 1][c - 1] 1) return ans; // 如果终点有障碍物直接返回空/* 动态规划求解可到达路径 */path[r - 1, c - 1] true;// 最右方边界判断for (int j c - 2; j 0; j--)if (path[r - 1, j 1] obstacleGrid[r - 1][j] 0)path[r - 1, j] true;// 最下方边界判断for (int i r - 2; i 0; i--)if (path[i 1, c - 1] obstacleGrid[i][c - 1] 0)path[i, c - 1] true;// 中间判断for (int i r - 2; i 0; i--)for (int j c - 2; j 0; j--)if (obstacleGrid[i][j] 0 (path[i 1, j] || path[i, j 1]))path[i, j] true;if (!path[0, 0]) return ans; // 如果起点没有可到达路径返回空/* 求解一条可到达路径 */int x 0, y 0;while (x ! r - 1 || y ! c - 1) {ans.Add(new Listint { x, y }); // 添加路径if (y 1 c path[x, y 1]) y; // 优先向右走else x; // 右方堵住则向下走}ans.Add(new Listint { r - 1, c - 1 }); // 添加终点return ans;}
}时间132 ms击败 100.00% 使用 C# 的用户内存42.62 MB击败 100.00% 使用 C# 的用户
