【题12矩阵中的路径，13 机器人的运动范围】Java实现

约定不等于承诺〃 2022-03-28 08:52 100阅读 0赞

**回溯法：**

*  回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步选择了其中一个选项时，就进入了下一步，然后又面临新的选项。就这样重复选择，直至到达最终的状态。
 *  用回溯法解决的问题的所有选项可以形象地用树状表示。

**【题12矩阵中的路径，13 机器人的运动范围】**  
**【题12矩阵中的路径】**  
**【题目】**  
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径，路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左，右，上，下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再此进入该格子。

**例如：**  
在下面的3 \* 4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子后，路径不能再次进入这个格子。  
a b t g  
c f c s  
j d e h

**分析：**  
矩阵的第一行第二个字母“b”和路径“bfce”的第一个字符相等。根据题目要求，  
（1）此时有3个选项，左a、右t、下f，a、t都不可以，尝试f。  
（2）f有3个选项，左c，右c，下d，左c可以，之后下j不符合。下d不符合，右c。  
（3）c有2个选项，右s和下e，右s不符合，下e符合。

**如图**  
![在这里插入图片描述][2019011009335410.png]

*  回溯法的递归特性，路径可以被看成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这时只好在路径上回到第n-1个字符，重新定位第n个字符。
 *  由于路径 不能重复进入矩阵的格子，所有还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入了每个格子。

**实现**

package ti12;
    
    import java.util.Scanner;
    
    public class StringPathInMatrix {
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
        {
            if (matrix == null || str == null || matrix.length < 1|| matrix.length<str.length) return false;
            boolean[] visited = new boolean[rows*cols];
            int curLength = 0;
            for (int i = 0;i < rows;++i) {
                for (int j = 0; j < cols; ++j) {
                    if (coreHasPath(matrix,rows,cols,i,j,str,visited,curLength)) return true;
                }
            }
            return false;
        }
        private boolean coreHasPath(char[] matrix, int rows, int cols, int row, int col, char[] str, boolean[] visited, int curLength) {
            if (curLength == str.length) return true;
            boolean hasPath = false;
            if (row>=0 && row < rows && col>=0 && col<cols && !visited[row*cols+col] && matrix[row*cols+col] == str[curLength]) {
                curLength++;
                visited[row*cols+col] = true;
                hasPath = coreHasPath(matrix,rows,cols,row-1,col,str,visited,curLength) ||
                        coreHasPath(matrix,rows,cols,row+1,col,str,visited,curLength) ||
                        coreHasPath(matrix,rows,cols,row,col-1,str,visited,curLength) ||
                        coreHasPath(matrix,rows,cols,row,col+1,str,visited,curLength);
                if (!hasPath) {
                    visited[row*cols+col] = false; //return hasPath回到上一层调用，curLength的值会自动回到上一层调用时的值
                }
            }
            return hasPath;
        }
     
     /*
        public static void main(String[] args) {
            char[] matrix = new char[]{'A','B','C','E','S','F','C','S','A','D','E','E'};
            char[] str = new char[]{'A','B','C','C','E','D'};
            StringPathInMatrix solution = new StringPathInMatrix();
            System.out.println("result "+solution.hasPath(matrix,3,4,str));
        }
    }
    */
    
        public static void main(String args[]){
    		
    		Scanner scanner = new Scanner(System.in);
    		
    		
    		System.out.println("请输入矩阵的行数：");
    		int rows = scanner.nextInt();
    		
    		System.out.println("请输入矩阵的列数：");
    		int cols = scanner.nextInt();
    		scanner.nextLine();
    		
    		System.out.println("请输入一个矩阵字符串，不包含空格：");
    		String tmp = scanner.nextLine();
    		
    		char[] arr = new char[tmp.length()];
    		arr = tmp.toCharArray();
    		
    		System.out.println("请输入要查询的字符串：");
    		String inputstr = scanner.nextLine();
    		char[] strarray = new char[inputstr.length()];
    		strarray = inputstr.toCharArray();
    		
    	//	char[][] arrays = new char[rows][cols];
    		
    	//	for(int i = 0; i < rows; i++){
    		//	for(int j = 0; j < cols; j++){
    				
    		//	}
    		//}
    		scanner.close();
    		StringPathInMatrix solution = new StringPathInMatrix();
    		System.out.println("矩阵中是否包含该字符串：");
    		System.out.println(solution.hasPath(arr, rows, cols, strarray));
    	}
    }

**代码解析**：

public class Solution {
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
            //标志位，初始化为false
            boolean[] flag = new boolean[matrix.length];
            for(int i =0;i < rows;i++){
                for(int j = 0;j<cols;j++){
                    //循环遍历二维数组，找到起点等于str第一个元素的值，再递归判断四周是否有符合条件的——回溯法
                    if(judge(matrix,i,j,rows,cols,flag,str,0)){
                        return true;
                    }
                }
            }
            return false;
        }
        //judge（初始矩阵，索引行坐标i，索引纵坐标j，矩阵行数，矩阵列数，待判断的字符串，字符串索引初始为0即先判断字符串第一位
        private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
            //先根据i和j计算匹配的第一个元素转为一位数组的位置
            int index = i*cols+j;
            //递归终止条件
            if(i<0||j<0||i>=rows||j>=cols||matrix[index] != str[k]||flag[index] == true){
                return false;
            }
            //若k已经到达str末尾了说明之前的都已经匹配成功了，直接返回true即可
            if(k == str.length-1){
                return true;
            }
            //要走的第一个位置置为true，表示已经走过了
            flag[index] = true;
            //回溯 递归寻找，每次找到了就给k加1，找不到，还原
            if(judge(matrix,i-1,j,rows,cols,flag,str,k+1)||
              judge(matrix,i+1,j,rows,cols,flag,str,k+1)||
              judge(matrix,i,j-1,rows,cols,flag,str,k+1)||
              judge(matrix,i,j+1,rows,cols,flag,str,k+1)){
                return true;
            }
            //走到这，说明这一条路不通，还原，再试其他路径
            flag[index] = false;
            return false;
        }
    
    
    }

**【题13 机器人的运动范围】**  
**【题目】**  
地上有一个m行n列的方格。一个机器人从坐标（0，0）的格子开始移动，它每次可以向左，右，上，下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。

**例如：**  
当k为18时，机器人能够进入方格（35，37），因为3+5+3+7=18.  
但它不能进入方格（35，38），因为3+5+3+8=19。  
请问该机器人能够到达多少个格子？

**分析**

*  和前面的题目类似，这个方格也可以看作一个m\*n的矩阵。同样，在这个矩阵中，除边界上的格子之外，其他格子都有4个相邻的格子
 *  机器人从坐标（0，0）开始移动。当它准备进入坐标（i，j）的格子时，通过检查坐标的数位和来判断机器人是否能够进入，则再判断它能否进入4个相邻的格子（i,j-1）、(i-1,j)、(I,j+1)、(i+1，j)。因此可以用回溯法实现。

**实现**

public class Solution {
        public int movingCount(int threshold, int rows, int cols) {
            int flag[][] = new int[rows][cols];
            return process(0, 0, rows, cols, flag, threshold);
        }
      
        private int process(int i, int j, int rows, int cols, int[][] flag, int threshold) {
            if (i < 0 || i >= rows || j < 0 || j >= cols || numSum(i) + numSum(j)  > threshold || flag[i][j] == 1) return 0;   
            flag[i][j] = 1;
            return process(i - 1, j, rows, cols, flag, threshold)
                + process(i + 1, j, rows, cols, flag, threshold)
                + process(i, j - 1, rows, cols, flag, threshold)
                + process(i, j + 1, rows, cols, flag, threshold)
                + 1;
        }
      
        private int numSum(int i) {
            int a= 0;
            do{
                a+= i%10;
            }while((i = i/10) > 0);
            return a;
        }
    }

参考：  
（1）《剑指offer》  
（2）[https://blog.csdn.net/w13261711130/article/details/79974302][https_blog.csdn.net_w13261711130_article_details_79974302]  
（3）[https://blog.csdn.net/gg543012991/article/details/52900562][https_blog.csdn.net_gg543012991_article_details_52900562]  
（4）[https://blog.csdn.net/weixin\_37672169/article/details/80140375][https_blog.csdn.net_weixin_37672169_article_details_80140375]

[2019011009335410.png]: /images/20220328/0ff7a7d5f8b147d8807cc5f2218e7be3.png
[https_blog.csdn.net_w13261711130_article_details_79974302]: https://blog.csdn.net/w13261711130/article/details/79974302
[https_blog.csdn.net_gg543012991_article_details_52900562]: https://blog.csdn.net/gg543012991/article/details/52900562
[https_blog.csdn.net_weixin_37672169_article_details_80140375]: https://blog.csdn.net/weixin_37672169/article/details/80140375