题解 | #矩阵中的路径#

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    Boolean isContain = false;
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        int xlength = matrix.length;
        int ylength = matrix[0].length;
        int[][] visit = new int[xlength][ylength];
        Stack<int[]> stack = new Stack ();//stack存路径,类似BFS广搜路径close表，但stack只存当前条路径，弹出后再存别条的路径，BFS的close表存所有经过的路径
        char[] wordc = word.toCharArray();
        for (int i = 0; i < xlength; i++) {
            for (int j = 0; j < ylength; j++) {
                int[] xy = {i, j};
                stack.push(xy);
                // stackc.push(wordc[0]);
                if (matrix[i][j] == wordc[0]) {
                    dfs(xy, stack, wordc, 0, matrix, xlength, ylength, visit);
                    if (isContain) {
                        return true;
                    }
                }
                stack.pop();
            }
        }
        return false;
    }
    public void dfs( int[] xy, Stack<int[]> stack, char[] wordc, int num,
                     char matrix[][], int xlength, int ylength, int[][] visit) {
        System.out.println("num:" + num);     //stack 存储路径
        System.out.println("w:" + wordc.length);      //stack 存储路径

        if (num == ( wordc.length - 1)) {
            isContain = true;
            return;
        }
        if (!stack.isEmpty()) {
            if (stack.size() > 0) {
                for (int i = -1; i < 2; i++)
                    for (int j = -1; j < 2; j++) {
                        if (i != j &&
                                i != -1 * j) {//满足条件的i,j组合为{-1,0},{0,-1},{1,0},{0,1}，即上下左右四个方向
                            int posX = stack.peek()[0] + i;
                            int posY = stack.peek()[1] + j;
                            num = num + 1;
                            if (posX < xlength && posX >= 0 && posY < ylength && posY >= 0) {
                                if (matrix[posX][posY] == wordc[num] && visit[posX][posY] == 0 ) {
                                    visit[posX][posY] = 1;
                                    int[] xyadd = {posX, posY};
                                    stack.push(xyadd);
                                    //递归之前的为本条递归的内容，直到尽头
                                    dfs(xy, stack, wordc, num, matrix, xlength, ylength, visit);
                                    //递归之后（也是递归到达尽头后）的为下条递归设置的条件
                                    //回溯，为另分一个分支接下来的递归设置条件，不是全部置空
                                    stack.pop();
                                    visit[posX][posY] = 0;
                                }
                            }
                            num = num - 1;
                        }
                    }
            }
        }
    }
    //递归里用return的话要把return结果返回给上次递归，不然会返回值覆盖（相当于多个返回结果）
}