矩阵中的路径

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        int m = matrix.length;
        int n = matrix[0].length;
        if (m == 0 || n == 0) return false;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backTrack(matrix, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    HashSet<String> visited = new HashSet<>();
    private boolean backTrack(char[][] matrix, String word, int i, int j, int idx) {
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length ||
                visited.contains(String.valueOf(i) + "," + String.valueOf(j))) {
            return false;
        }

        if (matrix[i][j] != word.charAt(idx)) {
            return false;
        }

        if (idx >= word.length()-1) {
            return true;
        }

        visited.add(String.valueOf(i) + "," + String.valueOf(j));
        boolean up = backTrack(matrix, word, i - 1, j, idx + 1);
        boolean down = backTrack(matrix, word, i + 1, j, idx + 1);
        boolean left = backTrack(matrix, word, i, j - 1, idx + 1);
        boolean right = backTrack(matrix, word, i, j + 1, idx + 1);
        visited.remove(String.valueOf(i) + "," + String.valueOf(j));

        return up || down || left || right;
    }
}

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    static boolean flag = false;
    boolean[][] used;
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        used = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (!flag) {
                    process(matrix, word, "", 0, i, j);
                }
            }
        }
        return flag;
    }
    public void process(char[][] matrix, String word, String cur, int num, int i,
                        int j) {
        if (i < 0 || j < 0 || i == matrix.length || j == matrix[0].length) {
            return;
        }
        if (!flag && num == word.length()) {
            if (cur.equals(word)) {
                flag = true;
            }
            return;
        }
        if (!flag && !used[i][j] && matrix[i][j] == word.charAt(num)) {
            used[i][j] = true;
            cur += matrix[i][j];
            if (cur.equals(word)) {
                flag = true;
            }
            process(matrix, word, cur, num + 1, i + 1, j);
            process(matrix, word, cur, num + 1, i - 1, j);
            process(matrix, word, cur, num + 1, i, j + 1);
            process(matrix, word, cur, num + 1, i, j - 1);
            used[i][j] = false;
        }
    }
}

 //记录word首字母每次出现时和坐标的对应关系,string的第一位是横坐标,第二位是纵坐标
    HashMap<Integer, String> map = new HashMap<>();
    //word首字母在矩阵中出现的次数
    int times = 0;
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        Boolean result = false;
        //成功的次数
//         int success = 0;
        if (matrix == null || matrix.length == 0) {
            result = false;
        }
        int n = matrix.length;
        int m = matrix[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == word.charAt(0)) {
                    times++;
                    map.put(times, i + "," + j);
                }
            }
        }
        //按照word首字母出现的次数,依次重新开始规划路线
        for (int t = 1; t <= times; t++) {
            String[] strs = map.get(t).split(",");
//             System.out.println(t + "======");
//             System.out.println("times="+times);
            int x = Integer.parseInt(strs[0]);
            int y = Integer.parseInt(strs[1]);
//             System.out.println("===" + x + "===" + y);
            int k = 0;
            //初始化flag矩阵记录是否走过
            Boolean[][] flag = new Boolean[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    flag[i][j] = false;
                }
            }
            for (int i = x; i < n; i++) {
                for (int j = y; j < m; j++) {
                    if (dfs(matrix, n, m, i, j, word, k, flag)) {
                        result = true;
                    }
                }
            }
//             System.out.println("");
//             System.out.println("");
            //如果返回结果为true,即已经找到完整路径,给本次循环也输出true
            if (result == true) {
//                 success+=1;
//                 System.out.println("true"+"第"+t+"次循环时成功,"+"共成功"+success+"次!");
                break;
            }
        }
        return result;
    }

    private boolean dfs(char[][] matrix, int n, int m, int i, int j, String word, int k, Boolean[][] flag) {
        //判断二维数组坐标是否与字符串当前下标的字符相等并且二维数组坐标是否为false(未使用)
        if (k >= word.length()) {
//            for(int )
            return true;
        }
        if (i < 0 || i >= n || j < 0 || j >= m) {
            return false;
        }
//         System.out.println(k + "===" + word.charAt(k));
//         System.out.println(i + "+++" + j + matrix[i][j]);


        //当某个节点有多条路径时执行的方法
        if (matrix[i][j] == word.charAt(k) && !flag[i][j]) {
            flag[i][j] = true;
            //验证当前节点是否有多个下一步,并记录当前状态下的i,j,k,flag,times状态
            Boolean[] result = new Boolean[4];
            result[0] =dfs(matrix, n, m, i - 1, j, word, k + 1, flag);
            result[1] =dfs(matrix, n, m, i + 1, j, word, k + 1, flag);
            result[2] =dfs(matrix, n, m, i, j - 1, word, k + 1, flag);
            result[3] =dfs(matrix, n, m, i, j + 1, word, k + 1, flag);
            if (result[0]||result[1]||result[2]||result[3]) {
                return true;
            }
        }
        flag[i][j] = false;
        return false;
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    char[] arr;
    int[][] log;
    int len;// 相当于x
    int len2; //相当于y
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        if(word.equals("")){
            return false;
        }
        arr=word.toCharArray();
        len=matrix[0].length;
        len2=matrix.length;
        log=new int[len2][len];
        for(int i=0;i<len2;i++){
            for(int j=0;j<len;j++){
                if(matrix[i][j]==arr[0]){
                   // log[i][j]=1;
                    boolean flag=choose(i,j,matrix,0);
                    if(flag){
                        return true;
                    }
                    //log[i][j]=0;
                }
                
            }
        }
        return false;
    }
    
    public boolean choose(int y,int x,char[][] matrix,int index){
        if(index>=arr.length){
            return true;
        }
                //看边界
        if(y<0||y>=len2){
            return false;
        }else if(x<0||x>=len){
            return false;
        }
         if(log[y][x]==1){
             return false;
         }

        if(matrix[y][x]==arr[index]&&log[y][x]==0){
            log[y][x]=1;    //说明使用了
            //说明找到
            boolean flag=choose(y-1,x,matrix,index+1)||choose(y+1,x,matrix,index+1)
                ||choose(y,x+1,matrix,index+1)||choose(y,x-1,matrix,index+1);
            if(flag){
                return true;
            }
            log[y][x]=0;
        }
        return false;
        
    }
}

 public boolean hasPath (char[][] matrix, String word) {
        char[] cc = word.toCharArray();
        int row = matrix.length;
        int col = matrix[0].length;
        boolean[][] isVisited = new boolean[row][col];
        for(int i = 0 ; i < row ; i ++) {
            for(int j = 0 ; j < col ; j ++) {
                int k = 0;
               if(matrix[i][j] == cc[k]) {
                   if(dfs(matrix,cc,isVisited,i,j,k)) {
                       return true;
                   }
               }
            }
        }
        return false;
    }
    private boolean dfs(char[][] matrix,char[] cc , boolean[][] isVisited,int row,int col,int k) {
        if(row < 0 || row > matrix.length-1 || col < 0 || col > matrix[0].length-1 || isVisited[row][col] || matrix[row][col] != cc[k]) return false;
        if(k == cc.length - 1) return true;
        ++ k ;
        isVisited[row][col] = true;
        if(dfs(matrix,cc,isVisited,row+1,col,k) || dfs(matrix,cc,isVisited,row-1,col,k) || dfs(matrix,cc,isVisited,row,col+1,k)
            || dfs(matrix,cc,isVisited,row,col-1,k)){
            return true ;
        }
        isVisited[row][col] = false;
        return false ;
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        char[] words = word.toCharArray();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++)
                if (bfs(matrix, words, i, j, 0)) return true;
        }
        return false;
    }
    public boolean bfs (char[][] matrix, char[] words, int i, int j, int index) {
        if (i < 0 || i>=matrix.length || j < 0 || j >=matrix[0].length || matrix[i][j] != words[index])
            return false;
        char tmp = matrix[i][j];
        matrix[i][j] = '.';
        if (index == words.length-1) return true;
        boolean result =  bfs(matrix, words, i-1, j, index + 1) ||
            bfs(matrix, words, i+1, j, index + 1) ||
            bfs(matrix, words, i, j-1, index + 1) ||
            bfs(matrix, words, i, j+1, index + 1);
        matrix[i][j] = tmp;
        return result;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if((matrix[i][j]==word.charAt(0)) 
                   && dfs(matrix,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] matrix, String word, int i,int j,int cur){
        if(word.length()==cur){
            return true;
        }
        if(i<0 || i>=matrix.length || j<0 || j>=matrix[0].length){
            return false;
        }
        if(matrix[i][j]!=word.charAt(cur) || matrix[i][j]=='0'){
            return false;
        }
        char temp = matrix[i][j];
        matrix[i][j] = '0';
        boolean flag = dfs(matrix,word,i-1,j,cur+1)
            || dfs(matrix,word,i+1,j,cur+1)
            || dfs(matrix,word,i,j-1,cur+1)
            || dfs(matrix,word,i,j+1,cur+1);
        matrix[i][j] = temp;
        return flag;
        
    }
}

import java.util.*;
public class Solution {
    char[][] matrix;
    String word;
    public boolean hasPath (char[][] matrix, String word) {
        // 使用递归完成回溯
        this.matrix = matrix;
        this.word = word;
        // 对每个节点dfs
        for(int row=0;row<matrix.length;row++){
            for(int col=0;col<matrix[0].length;col++){
                // 一旦找到则直接返回
                if(recur(row,col,0)==true){
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean recur(int row, int col, int len){
        // 以当前坐标为起点，向四个方向递归搜索
        
        // 如果当前递归target长度==word长度，返回true
        if(len==word.length())
            return true;
        // 如果越界，返回false
        if(row<0 || col<0 || row>=matrix.length || col>=matrix[0].length)
            return false;
        // 如果当前坐标值==特殊值，说明往回找到了用过的点，返回false
        if(matrix[row][col]=='_')
            return false;
        // 如果当前坐标值不等于下一个需要的值，返回false
        if(matrix[row][col]!=word.charAt(len))
            return false;
        // 暂存当前值，以特殊值标记当前节点为“用过”
        char temp = matrix[row][col];
        matrix[row][col] = '_';
        // 如果到这一步还没终止递归，说明截至到现在是一路匹配下来的，继续向四个方向递归, 暂存当前结果
        boolean result = recur(row+1,col,len+1) || recur(row,col+1,len+1) || recur(row-1,col,len+1) || recur(row,col-1,len+1);
        // 恢复当前值
        matrix[row][col] = temp;
        // 返回结果
        return result;
    }
}