题解 | #矩阵中的路径#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public char[]arr; 
    public boolean ans = false;
    public int []dx = {0,-1,0,1};
    public int []dy = {-1,0,1,0};
    public boolean hasPath (char[][] m, String w) {
        // write code here
        this.arr = w.toCharArray();
        int c = m.length;
        int r = m[0].length;
        for ( int i = 0; i < c; ++i ) {
            for ( int j = 0; j < r; ++j ) {
                boolean[][] v = new boolean[c][r];
                dfs(0,i,j,v,m);
                if (this.ans) return true;
            }
        }
        return this.ans;
    }

    public void dfs(int n,int x,int y,boolean[][]v,char[][]m){
        if ( n >= this.arr.length) {
            this.ans = true;
            return ;
        }
        if (x < 0 || y < 0 || x >= v.length || y >= v[0].length) return;
        if (this.arr[n] != m[x][y] ) return;
        if (v[x][y]) return;
        v[x][y] = true;
        for ( int i = 0; i < 4; ++i ) {
            dfs(n+1,x+this.dx[i],y+this.dy[i],v,m);
        }
	    // 恢复现场
        v[x][y] = false;
    }
}