记录大佬代码_抱拳规范
矩阵中的路径
http://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
public class Solution { public int[][] visit; //全局定义visit矩阵,拜访过的节点为1 public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { visit = new int[rows][cols];//初始化拜访矩阵 char[][] array = new char[rows][cols]; for (int i = 0; i < rows ; i++) {//这部分非必要,转化后好理解 for(int j = 0; j < cols; j++) {//将矩阵转化为二维矩阵 array[i][j] = matrix[i*cols + j]; } } for (int i = 0; i < rows ; i++) {//遍历矩阵中每一个元素 for(int j = 0; j < cols; j++) { if(find(array,rows,cols,str,i,j,0)){//进入回溯 return true; } } } return false; } public boolean find(char[][] array, int rows, int cols, char[] str, int rpos,int cpos, int spos) { /* 1.array:原始数组 2.rows:数组行数 3.cols:数组列数 上述说非必要的原因就是这里冗余了信息(行列数目) 4.str:需要匹配的char[] 5.rpos:行位置 6.cpos:列位置 7:spos:匹配到了第几个字符 */ if(spos >= str.length) {//如果匹配字符数和str长度一致,说明匹配完成 return true; } if(rpos < 0 || cpos < 0 || rpos >= rows || cpos >= cols || array[rpos][cpos] != str[spos] || visit[rpos][cpos] == 1) {//如果rpos<0等条件下,说明遇到边界。无法继续 return false; } visit[rpos][cpos] = 1;//拜访矩阵目前元素访问过,flag变为1 boolean isSunc = find( array, rows, cols, str, rpos+1, cpos, spos+1)//↓ || find( array, rows, cols, str, rpos , cpos+1, spos+1)//→ || find( array, rows, cols, str, rpos-1, cpos, spos+1)//↑ || find( array, rows, cols, str, rpos , cpos-1, spos+1);//← visit[rpos][cpos] = 0;//拜访矩阵置为0,继续下一次回溯 return isSunc;//返回最终结果 } }