矩阵中的路径
矩阵中的路径
http://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
题目描述:
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。
思路
使用递归和回溯的思想,回溯思想:设置一个标记矩阵,矩阵与原本矩阵相同,true表示走过了,false表示没走过,当这条路径不匹配的时候,再把原来标记位true的标记位false;
public class Solution { public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) { //把一维数组转换成二维的 char[][] board = new char[rows][cols]; int ceng = 0 ; int x =0 ; for(int i =0 ;i<matrix.length ;i++){ if(x == cols) { x= 0; ceng++; } board[ceng][x] = matrix[i]; x++; } for(int i =0 ;i<rows ;i++){ for(int j = 0;j<cols;j++){ System.out.print(board[i][j]); } System.out.println(); } // boolean vis[][] = new boolean[rows][cols]; int index = 0; // for(int i =0 ;i<rows ;i++){ for(int j = 0;j<cols;j++){ if(solve(board,str,i,j,vis,index) == true) { return true; } } } return false; } private static boolean solve(char[][] board, char[] str, int i, int j, boolean[][] vis,int index) { //处理越界 if(i< 0|| i>board.length-1 || j<0 ||j>board[0].length-1 || vis[i][j]) { return false; } //匹配到不满足的情况 if(str[index] != board[i][j]) { return false; } //匹配成功 if(index == str.length-1) { return true; } vis[i][j] = true; boolean flag = solve(board,str,i+1,j,vis,index+1)|| //向下 solve(board,str,i-1,j,vis,index+1)|| //向上 solve(board,str,i,j+1,vis,index+1)|| //向右 solve(board,str,i,j-1,vis,index+1); //向左 vis[i][j] = false; return flag; } }