算法题解：走方格问题大汇总（持续更新JAVA代码）

浅浅的花香味﹌ 2023-06-25 12:30 11阅读 0赞

Q1. 在给定的Matrix中寻找路径  
给定一个二维数组，求是否存在一条从左上角移动到右下角的路径。在给定的二维数组中，单元格的值为-1时表示不能通过；单元格的值为0时，表示可以通过。

例如：给定一个二维数组如下：

\{ 0, 0, 0, -1, 0\},  
\{-1, 0, 0, -1, -1\},  
\{ 0, 0, 0, -1, 0\},  
\{-1, 0, 0,  0, 0\},  
\{ 0, 0, -1,  0, 0\}  
   
路径存在，返回YES  
   
\{ 0, 0, 0, -1, 0\},  
\{-1, 0, 0, -1, -1\},  
\{ 0, 0, 0, -1, 0\},  
\{-1, 0, -1,  0, 0\},  
\{ 0, 0, -1,  0, 0\}  
路径不存在，返回NO

算法分析

这个问题简单的解决方法是通过 BFS 或 DFS 算法来查找是否存在符合条件的路径（Path）。

更好的解决方法是通过将所有可访问节点的值更改为1来标记它们。

首先，将左上角第一个元素的值标记为1。然后在第一行中获取下一个（当前）值并与前一个值进行比较。仅当当前值可到达时（不等于-1），才将其设置为前一个值。同样，对列值执行相同的操作，方法是将当前值与前一列的值（如果可以访问）进行比较并设置。

然后从第一行和第一列开始，并获取前一行和前一列的值。找到它们之间的最大值，并将当前索引设置为该最大值。如果当前索引值为-1，则不会有任何更改。

最后，如果右下角的最终索引为1，则返回“是”，否则返回“否”。

package com.bean.algorithm.basic;  
   
public class FindthePathinMatrix \{  
   
    // 寻找是否存在一条路径从左上角通向右下角  
    static boolean isPath(int arr\[\]\[\]) \{  
          
        int row=arr.length;  
        int col=arr\[0\].length;  
          
        // 设置左上角的第一个元素值为1，即 arr\[0\]\[0\] = 1  
        arr\[0\]\[0\] = 1;  
   
        //标记从左上到右下的元素位置是否可以访问（visited）从第1行第1列开始  
        for (int i = 1; i < col; i++) \{  
            if (arr\[0\]\[i\] != -1) \{  
                arr\[0\]\[i\] = arr\[0\]\[i - 1\];  
            \}  
                  
        \}  
              
        for (int j = 1; j < row; j++) \{  
            if (arr\[j\]\[0\] != -1) \{  
                arr\[j\]\[0\] = arr\[j - 1\]\[0\];  
            \}  
                  
        \}  
              
        //在剩余的Matrix中做好标记  
        for (int i = 1; i < row; i++) \{  
            for (int j = 1; j < col; j++) \{  
                if (arr\[i\]\[j\] != -1) \{  
                    arr\[i\]\[j\] = Math.max(arr\[i\]\[j - 1\], arr\[i - 1\]\[j\]);  
                \}  
            \}  
        \}  
          
        // 如果右下角的元素为1，则返回 yes；表示路径存在   
        return (arr\[5 - 1\]\[5 - 1\] == 1);  
    \}  
   
      
    public static void main(String\[\] args) \{  
          
        int arr\[\]\[\] = \{   
                \{ 0,  0, 0, -1, 0 \},   
                \{ -1, 0, 0, -1, -1 \},   
                \{ 0,  0, 0, -1, 0 \},   
                \{ -1, 0, -1, 0, -1 \},  
                \{ 0,  0, -1, 0, 0 \}   
                \};  
   
        // 从左上角第一个元素开始  arr\[0\]\[0\] 一直到右下角的元素结束 arr\[row\]\[col\]  
        if (isPath(arr)) \{  
            System.out.println("Yes");  
        \}else \{  
            System.out.println("No");  
        \}  
    \}  
\}  
程序运行结果：

Q2. 在给定的Matrix中求从第一行到最后一行路径的最大累加和  
给定一个N\*M的矩阵（N行，M列），求矩阵中的最大路径和。

最大路径是从第一行到最后一行路径上的所有元素的总和。在移动过程中，只允许从上向下或从左向右移动，或对角线方向（从左上到右下，或者从右上到左下）移动。您可以从第一行中的任何元素开始。

举例：

10 10  2  0 20  4  
1  0  0 30  2  5  
0 10  4  0  2  0  
1  0  2 20  0  4  
   
输出结果为: 74  
最大路径是从：20 - 30 - 4 - 20  
   
   
1 2 3  
9 8 7  
4 5 6  
   
输出结果为：17  
最大路径是从：3 - 8 - 6  
   
算法设计  
package com.bean.algorithm.basic;  
   
public class MaximumPathSuminMatrix \{  
      
      
    /\*  
     \* 走方格：  
     \* 规则是从第一行到最后一行，经过的单元格元素值累加和最大。  
     \* 移动方向：从上到下，对角方向移动  
     \* 找到一条路径，使得该路径上单元格中的值累加和最大。  
     \* \*/  
    static int findMaxPath(int mat\[\]\[\]) \{  
          
        int N=mat.length; //表示矩阵的行数  
        int M=mat\[0\].length; //表示矩阵的列数  
          
        // 初始化返回值 result = -1  
        int result = -1;  
          
        for (int i = 0; i < M; i++) \{  
            result = Math.max(result, mat\[0\]\[i\]);  
        \}  
   
        for (int i = 1; i < N; i++) \{  
            result = -1;  
            for (int j = 0; j < M; j++) \{  
                // When all paths are possible  
                if (j > 0 && j < M - 1) \{  
                    mat\[i\]\[j\] += Math.max(mat\[i - 1\]\[j\], Math.max(mat\[i - 1\]\[j - 1\], mat\[i - 1\]\[j + 1\]));  
                \}else if (j > 0) \{  
                    mat\[i\]\[j\] += Math.max(mat\[i - 1\]\[j\], mat\[i - 1\]\[j - 1\]);  
                \}else if (j < M - 1) \{  
                    mat\[i\]\[j\] += Math.max(mat\[i - 1\]\[j\], mat\[i - 1\]\[j + 1\]);  
                \}  
   
                // 得到返回值result。返回值应该是 mat\[i\]\[j\]与result中较大者。  
                result = Math.max(mat\[i\]\[j\], result);  
            \}  
        \}  
        return result;  
    \}  
   
    public static void main(String\[\] args) \{  
        int mat\[\]\[\] = \{   
                \{ 10, 10, 2, 0, 20, 4 \},   
                \{ 1, 0, 0, 30, 2, 5 \},   
                \{ 0, 10, 4, 0, 2, 0 \},   
                \{ 1, 0, 2, 20, 0, 4 \}   
                \};  
   
        System.out.println(findMaxPath(mat));  
    \}  
\}  
程序运行结果：

Q3. 给定一个二维矩阵输出从左上角移动到右下角的所有可能路径（Path）  
问题描述：给定一个N行M列的二维矩阵，输出从左上角移动到右下角的所有可能路径。

约束条件是：每次只能向右移动或者向下移动。

例如：

给定二维矩阵为：

1 2 3  
4 5 6

输出路径：

1 4 5 6  
1 2 5 6  
1 2 3 6

给定二维矩阵为：

1 2   
3 4  
输出路径为：

1 2 4  
1 3 4

算法分析：该算法是一个简单的递归算法，从每个单元格开始，先向下打印所有路径，然后向右打印所有路径。对遇到的每个单元格递归执行此操作。

算法设计  
package com.bean.algorithm.basic;  
   
public class CountPathofMatrix2 \{  
   
   
    private static void printMatrix(int mat\[\]\[\], int m, int n, int i, int j, int path\[\], int idx) \{  
        path\[idx\] = mat\[i\]\[j\];  
   
        // Reached the bottom of the matrix so we are left with  
        // only option to move right  
        if (i == m - 1) \{  
            for (int k = j + 1; k < n; k++) \{  
                path\[idx + k - j\] = mat\[i\]\[k\];  
            \}  
            for (int l = 0; l < idx + n - j; l++) \{  
                System.out.print(path\[l\] + " ");  
            \}  
            System.out.println();  
            return;  
        \}  
   
        // Reached the right corner of the matrix we are left with  
        // only the downward movement.  
        if (j == n - 1) \{  
            for (int k = i + 1; k < m; k++) \{  
                path\[idx + k - i\] = mat\[k\]\[j\];  
            \}  
            for (int l = 0; l < idx + m - i; l++) \{  
                System.out.print(path\[l\] + " ");  
            \}  
            System.out.println();  
            return;  
        \}  
        // Print all the paths that are possible after moving down  
        printMatrix(mat, m, n, i + 1, j, path, idx + 1);  
   
        // Print all the paths that are possible after moving right  
        printMatrix(mat, m, n, i, j + 1, path, idx + 1);  
    \}  
   
    // Driver code  
    public static void main(String\[\] args) \{  
        int m = 2;  
        int n = 3;  
        int mat\[\]\[\] = \{ \{ 1, 2, 3 \}, \{ 4, 5, 6 \} \};  
        int maxLengthOfPath = m + n - 1;  
        printMatrix(mat, m, n, 0, 0, new int\[maxLengthOfPath\], 0);  
    \}  
\}  
程序输出结果：

1 4 5 6   
1 2 5 6   
1 2 3 6

Q4. 给定一个二维矩阵输出从左上角移动到右下角的所有可能路径（Path）的数量  
问题描述：给定一个N行M列的二维矩阵，输出从左上角移动到右下角的所有可能路径。

约束条件是：每次只能向右移动或者向下移动。

例如：在Q3.问题中列出了所有的可能路径，Q4不要求列出所有可能的路径，而是根据N行M列来统计所有可能路径的数量。

算法分析  
该问题可以采用动态规划算法来解决。

算法设计  
public static int countMatrixPath(int m, int n) \{  
           
        /\*  
         \* 开辟一个动态数组dp;dp数组的大小和原方格大小相同。  
         \* 定义dp\[i\]\[j\]表示从左上角的格子（原点或者起点）走到nums\[i\]\[j\]的格子共有多少种走法。  
         \* 首先分析题目的状态转移方程：因为机器人只能向右或向下走，  
         \* 对于非边界的每一个格子nums\[i\]\[j\],都有:dp\[i\]\[j\]=dp\[i-1\]\[j\]+dp\[i\]\[j-1\]  
         \* 然后考虑边界条件:  
         \* 当i=0时,机器人只能向右走,  
         \* 当j=0时,只能向下走,  
         \* 所以对于边界点nums\[i\]\[j\]有,  
         \* 当i=0时,有dp\[i\]\[j\]=dp\[i\]\[j-1\];(表示当前位置是从左向右走过来的)  
         \* 当j=0时,有dp\[i\]\[j\]=dp\[i-1\]\[j\];(表示当前位置是从上向下走过来的)  
         \*    
         \* \*/  
        int\[\]\[\] dp = new int\[m\]\[n\];  
   
        for (int i = 0; i < m; i++) \{  
            for (int j = 0; j < n; j++) \{  
                  
                if (i != 0 || j != 0) \{// 避免i,j同时为0,数组下标越界  
                    if (i == 0) \{//边界条件：表示从左向右走  
                        dp\[i\]\[j\] = dp\[i\]\[j - 1\];  
                    \}  
                    else if (j == 0) \{//边界条件：表示从上向下走  
                        dp\[i\]\[j\] = dp\[i - 1\]\[j\];  
                    \}  
                    else \{  
                        //对于非边界上的格子  
                        dp\[i\]\[j\] = dp\[i\]\[j - 1\] + dp\[i - 1\]\[j\];  
                    \}  
                \} else  
                    dp\[i\]\[j\] = 1;  
   
            \}  
        \}  
        //根据dp\[i\]\[j\]的定义，其表示从左上角的格子（起点）走到nums\[i\]\[j\]的格子共有多少种走法。  
        //返回dp\[m-1\]\[n-1\]的值。  
        return dp\[m - 1\]\[n - 1\];  
   
\}