首页 > 试题广场 >

走格子

[编程题]走格子
  • 热度指数:9560 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个n乘m的矩阵map,其中map[i][j]表示坐标为(i,j)的格子,值为1代表该格子不能通过,0代表可以通过。现从(0,0)的格子走到(n - 1,m - 1),单位时间只能走一格,不能途径无法通过的格子,请返回最短时间。同时给定矩阵的大小nm(n和m均小于等于100),并且一定能走到终点。

头像 天不生我李淳罡,剑道万古如长夜
发表于 2021-12-28 15:06:27
想要走到终点(n-1,m-1),那么必须先走到它的上面(n-2,m-1)或者左边(n-1,m-2);同理可知,走到任意一点(x,y),都必须可以走到这一点的上面或者左边,才能保证一定能走到终点。既然通向终点(n-1,m-1)路径上的点都必须首先它的上边或者左边,那么从起点到终点一定存在一条向右或向下 展开全文
头像 郭凯要加油
发表于 2022-03-25 18:45:30
class Flood { public: int MAX=1000; int floodFill(vector<vector<int> > map, int n, int m) { vector<vector<int>>dp(n,v 展开全文