本文共 1371 字，大约阅读时间需要 4 分钟。
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
例如下面的矩阵包含了一条 bfce 路径。
public class Path {
private final static int[][] next=new int[][] { {0,-1},{0,1},{-1,0},{1,0}}; int len; private static char[][] array; public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { this.len=str.length; array=new char[rows][cols]; boolean[][] flag=new boolean[rows][cols]; int idx=0; for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) { array[i][j]=matrix[idx]; flag[i][j]=false; idx=idx+1; } } int str_index=0; for(int i=0;i<rows;i++) //选择任意的一个进行开始 { for(int j=0;j<cols;j++) { if(backTrack(flag,rows,cols,i,j,str,str_index)) { return true; } } } return false; }private boolean backTrack(boolean[][] flag,int rows,int cols, int r, int c,char[] str,int str_index) {
if(str_index>=str.length) //已经全部访问完了 { return true; } if(r<0 || r>=rows || c<0 || c>=cols || array[r][c]!=str[str_index] || flag[r][c]) //边界判定条件 { return false; } flag[r][c]=true; for(int[] ele:next) //上下左右全部试过一次 { if(backTrack(flag,rows,cols,r+ele[0],c+ele[1],str,str_index+1)) { return true; } } flag[r][c]=false; return false; }public static void main(String[] args) {
String s="ABCESFCSADEE"; char[] matrix=s.toCharArray(); int a=3; int b=4; String d="ABCCED"; System.out.println(new Path().hasPath(matrix,a,b,d.toCharArray()));}
}
转载地址：http://fdkmi.baihongyu.com/