当前位置: 代码迷 >> 综合 >> JAVA算法:采用最少的步数(Step)到达二维矩阵的边界
  详细解决方案

JAVA算法:采用最少的步数(Step)到达二维矩阵的边界

热度:43   发布时间:2024-01-15 19:17:32.0

JAVA算法:采用最少的步数(Step)到达二维矩阵的边界

问题描述:

给定一个n x m矩阵,其中单元格的取值为0,或者1。0表示单元格为空;1表示单元格不为空。您的站位,在单元格中用2表示。

您可以垂直向上或向下、水平向左或向右移动到任何空单元格。

您的任务是找到能够到达该二维矩阵任何边界(边缘)的最小步数(Step)。

如果无法到达任何边界(边缘),请输出 -1。

注意:整个矩阵中只有一个值为2的单元格。

例如:

给定一个二维矩阵

  matrix[] = {1, 1, 1, 0, 1}
                  {1, 0, 2, 0, 1} 
                  {0, 0, 1, 0, 1}
                  {1, 0, 1, 1, 0} 
输出:2

解释:找到你的站位,然后向右移动,在向上移动,即可到达二维矩阵的边界。

给定一个二维矩阵

  matrix[] = {1, 1, 1, 1, 1}
                  {1, 0, 2, 0, 1} 
                  {1, 0, 1, 0, 1}
                  {1, 1, 1, 1, 1}
输出: -1 

解释:找到你的站位,你无法移动到该二维矩阵的边界。


问题分析

使用动态规划算法来解决该问题,思路如下:

  • 先找到你的站位