矩阵中的路径

思路

毋庸置疑最先想到回溯法。
说一个空间复杂度O(1)的。
走过的地块标为 ' ' 等不会用到的字符即可。
时间复杂度最差也不会到O(n2)，没时间没能力算具体多少，总之实际上不太多。
类似的问题如：填海造陆，离陆最远等dfs,bfs问题。

多说两句说一下思路吧。数组存储的矩阵的任意一点(i,j)在数组中的位置k=i*cols+j
（btw，k在矩阵一点的位置(k/cols, k%cols)）。
通过递归回溯，遍历数组，找从一点开始上下左右走且不重复的情况下，走出str路径的情况即可。

代码

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        for (int i = 0; i < matrix.length; i++) {
            if (findPath(matrix, cols, i, str, 0)) return true;
        }
        return false;
    }

    public boolean findPath(char[] matrix, int cols, int k, char[] str, int c) {
        if (c >= str.length) return true;
        if (k < 0 || k >= matrix.length || matrix[k] != str[c]) return false;
        int i = k / cols;
        int j = k % cols;
        char tmp = matrix[k];
        matrix[k] = ' ';
        if (findPath(matrix, cols, (i-1)*cols+j, str, c+1) ||
        findPath(matrix, cols, (i+1)*cols+j, str, c+1) ||
        findPath(matrix, cols, i*cols+j-1, str, c+1) ||
        findPath(matrix, cols, i*cols+j+1, str, c+1))
            return true;
        matrix[k] = tmp;
        return false;
    }

回溯，利用坐标映射无需构造二维数组
public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        for(int i=0;i<matrix.length;i++){
            if(judge(matrix,i,cols,str,0))
                return true;
        }
        return false;
    }
    
    public boolean judge(char[] matrix,int q, int cols, char[] str, int p){
        if(p==str.length)
            return true;
        if(q>=0 && q<matrix.length && matrix[q]==str[p]){
            matrix[q] = '#';
            boolean right = judge(matrix,q+1,cols,str,p+1);
            boolean left = judge(matrix,q-1,cols,str,p+1);
            boolean up = judge(matrix,q-cols,cols,str,p+1);
            boolean down = judge(matrix,q+cols,cols,str,p+1);
            matrix[q] = str[p];
            return right||left||up||down;
        }
        return false;
    }

}

public class Solution {
    private int[][] visited;
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
       visited = new int[rows][cols];
		for (int x = 0; x <= rows - 1; x++) {
			for (int y = 0; y <= cols - 1; y++) {
				if (findNext(matrix, rows, cols, x, y, str, 0)) {
					return true;
				}
			}
		}
		return false;
    }
    
    public boolean findNext(char[] matrix, int rows, int cols, int x, int y, char[] str, int k) {
		if (k == str.length) {
			return true;
		}
		if (x < 0 || y < 0 || x >= rows || y >= cols || visited[x][y] == 1) {
			return false;
		}
		if (str[k] != matrix[x * cols + y])
			return false;
		// 当前相同，按顺时针走
		visited[x][y] = 1;
		if (findNext(matrix, rows, cols, x + 1, y, str, k + 1))
			return true;
		if (findNext(matrix, rows, cols, x, y + 1, str, k + 1))
			return true;
		if (findNext(matrix, rows, cols, x - 1, y, str, k + 1))
			return true;
		if (findNext(matrix, rows, cols, x, y - 1, str, k + 1))
			return true;
		visited[x][y] = 0;
		return false;
	}


}

public class Solution {
    char[] matrix;
    int rows;
    int cols;
    char[] str;
    int[] visited;
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(matrix == null && str != null){
            return false;
        }
        if(str == null){
            return false;
        }
        this.matrix = matrix;
        this.rows = rows;
        this.cols = cols;
        this.str = str;
        // 标识matrix中元素有没有被访问
        visited = new int[matrix.length];
        // 第一行第二个就等于matrix[0*rows+1]
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                // 找到matrix中与str第一个字符相等的位置从这里开始
                if(matrix[i*cols+j] == str[0]){
                    boolean result = path(i,j,0);
                    if(result){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean path(int startRow, int startCol,int index){

        // 如果不相同说明这条路径不通需要回溯，或者这个节点已经走过
        if(matrix[startRow * cols +startCol] != str[index] || visited[startRow * cols +startCol] == 1){
            return false;
        }
        // 标记节点已经访问过
        visited[startRow * cols +startCol] = 1;
        // 说明已经到最后返回true,否则继续走
        if(index+1 >= str.length){
            return true;
        }
        // 向上走
        if(startRow-1 >= 0){
            if(path(startRow-1, startCol, index+1)){
                return true;
            }
        }
        // 向下走
        if(startRow+1 < rows){
            if(path(startRow+1, startCol, index+1)){
                return true;
            }
        }
        // 向左走
        if(startCol-1 >= 0){
            if(path(startRow, startCol-1, index+1)){
                return true;
            }
        }
        // 向右走
         if(startCol+1 < cols){
            if(path(startRow, startCol+1, index+1)){
                return true;
            }
        }
        // 回溯
        visited[startRow * cols +startCol] = 0;
        return false;
    }
}

class Solution {
    private final int [][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private boolean result = false;
    private boolean [][] vis;
    private boolean check(int rows, int cols, int nextX, int nextY) {
        return nextX < rows && nextX >= 0 && nextY < cols && nextY >= 0;
    }
    private void dfs(char[][] chs, int rows, int cols, char[] str, int x, int y, int curLen) {
        if (str.length <= curLen) {
            result = true;
            return;
        }
        if (!check(rows, cols, x, y) || vis[x][y] || chs[x][y] != str[curLen]) {
            return;
        }
        vis[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            dfs(chs, rows, cols, str, nextX, nextY, curLen + 1);
        }
        vis[x][y] = false;
    }
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix.length < str.length) {
            return false;
        }
        char [][] chs = new char[rows][cols];
        vis = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                chs[i][j] = matrix[i*cols + j];
                vis[i][j] = false;
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(chs, rows, cols, str, i, j, 0);
            }
        }
        return result;
    }
}

public class Solution {
    int row_nums;
    int col_nums;
    boolean[] visited;
    int pathLen;
    char[] str_check;

    public  boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        row_nums = rows;
        col_nums = cols;
        str_check = str;
        if (matrix.length == 0 || row_nums < 1 || col_nums < 1 || str_check.length == 0) {
            return false;
        }
        // 访问记录布尔数组
        visited = new boolean[rows * cols];
        // 字符串路径长度
        pathLen = 0;
        // 遍历矩阵中每一个元素判断能否存在以当前元素为起点的路径
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (hasPthCore(matrix, row, col)) {
                    return true;
                }
            }
        }
        return false;
    }

    private  boolean hasPthCore(char[] matrix, int row, int col) {
        int index = row*col_nums+col;
        boolean hasPath = false;
        // 路径长度等于校验串长度，则表示找到了，终止
        if(pathLen== str_check.length){
            return true;
        }
        // 设置终止条件,在行列范围内，且未访问过
        if (row >= 0 && row < row_nums 
                && col >= 0 && col < col_nums
                && matrix[index] == str_check[pathLen]
                && !visited[index]) {
            // 如果当前串比较字符与矩阵中字符相等,那么路径长度加一，设为已访问
            ++pathLen;
            visited[row * col_nums + col] = true;
            // 向四周扩展
            hasPath = hasPthCore(matrix, row, col - 1)
                    || hasPthCore(matrix, row, col + 1)
                    || hasPthCore(matrix, row - 1, col)
                    || hasPthCore(matrix, row + 1, col);
            // 回溯
            if (!hasPath) {
                --pathLen;
                visited[index] = false;
            }
        }
        return hasPath;
    }
}

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        boolean[][] isVisited = new boolean[cols][rows];
        for (int i = 0; i < cols; i++) {
            for (int j = 0; j < rows; j++) {
                if (judge(matrix, i, j, rows, cols, isVisited, str, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean judge(char[] matrix, int i, int j, int rows, int cols, boolean[][] isVisited, char[] str, int k) {
        if (i < 0 || j < 0 || i >= cols || j >= rows ||
                matrix[j * cols + i] != str[k] || isVisited[i][j]) {
            return false;
        }
        if (k == str.length - 1) return true;
        isVisited[i][j] = true;
        if (judge(matrix, i - 1, j, rows, cols, isVisited, str, k + 1) ||
            judge(matrix, i + 1, j, rows, cols, isVisited, str, k + 1) ||
            judge(matrix, i, j - 1, rows, cols, isVisited, str, k + 1) ||
            judge(matrix, i, j + 1, rows, cols, isVisited, str, k + 1))
            return true;
        isVisited[i][j] = false;
        return false;
    }
}

public class Solution {
    
    private int rows;
    private int cols;
    private char[] matrix;
    private char[] str;
    
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {

        this.rows = rows;
        this.cols = cols;
        this.matrix = matrix;
        this.str = str;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (step(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean step(int i, int j, int s) {
        if (i < 0 || i >= rows) {
            return false;
        }
        if (j < 0 || j >= cols) {
            return false;
        }
        int pos = i * cols + j;
        if (matrix[pos] != str[s]) {
            return false;
        }
        if (s == str.length - 1) {
            return true;
        }
        char tmp = str[s];
        matrix[pos] = ' ';
        boolean found = step(i-1, j, s+1)
            || step(i+1, j, s+1)
            || step(i, j-1, s+1)
            || step(i, j+1, s+1);
        
        if (found) {
            return true;
        }
        matrix[pos] = tmp;
        return false;
    }
}

public class Solution {
    /**
    经典的回溯
    遍历数组所有元素
    每个元素去找是否是有这样的路径
    */
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if (null == matrix || matrix.length == 0 || rows < 1 || cols < 1
           || null == str || str.length == 0) {
            return false;
        }
        boolean visited[] = new boolean[matrix.length]; //是否被访问过
        int k = 0; //参与匹配的str的下标
        for(int i=0; i<rows; i++) {
            for(int j=0; j<cols; j++){
                if (hasPath(matrix, rows, cols, i, j, str, k, visited)){
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean hasPath(char[] matrix, int rows, int cols, 
                            int row, int col, char[] str, int k, boolean visited[]) {
        if (k == str.length) {
            return true;
        }
        boolean result = false;
        if (row>= 0 && row < rows && col < cols && col >= 0
            && matrix[row*cols+col] == str[k] && !visited[row*cols+col]) { //匹配成功
            visited[row*cols+col] = true; //访问过
            k++; //匹配下一个
            result = hasPath(matrix, rows, cols, row-1, col, str, k, visited) //上
                || hasPath(matrix, rows, cols, row+1, col, str, k, visited) //下
                || hasPath(matrix, rows, cols, row, col-1, str, k, visited) //左
                || hasPath(matrix, rows, cols, row, col+1, str, k, visited); //右
            if(!result) {
                k--;
                visited[row*cols+col] = false; //此路不通，设为没访问过
            }    
        }
        return result;
    }


}

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        char[][] map = new char[rows][cols];
        int[][] visited = new int[rows][cols];
        
        for (int i=0;i<rows;i++) {
            for (int j=0;j<cols;j++) {
                map[i][j] = matrix[i * cols + j];
            }
        }
        for (int i=0;i<rows;i++) {
            for (int j=0;j<cols;j++) {
                if ( hasStep(map, visited, i, j, str, 0) ) {
                    return true;
                }
            }
        }
        return false;
    }
    boolean hasStep(char[][] map, int[][] visited, int x, int y, char[] str, int index) {
        if (x < 0 || x >= map.length || y < 0 || y >= map[0].length
           || str[index] != map[x][y]
           || visited[x][y] == 1) {
            return false;
        }
        if (index == str.length-1) {
            return true;
        }
        visited[x][y] = 1;
        
        boolean flag = hasStep(map, visited, x-1, y, str, index+1)
            || hasStep(map, visited, x+1, y, str, index+1)
            || hasStep(map, visited, x, y-1, str, index+1)
            || hasStep(map, visited, x, y+1, str, index+1);
        visited[x][y] = 0;
        return flag;
    }

}

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

讲讲为什么用DFS，而不能用BFS （个人看法，有误请批！）
这道题首先看出是DFS（深搜）问题，（为何是DFS，DFS就是用来不停探寻下一步，直至能否到达目的点，而另一种是BFS（广搜），BFS是用来找到源点到终点的最短路径。如果用BFS求解这道题，嗯？确定能用吗?BFS是以源点向四周扩散，以最短的扩散次数找到源点，听起来好像可以，我们可以一次次扩散找到路径中的每一个点，但是一般的BFS扩散一次，会把走过的结点标志为不可以走，那么假如第一个结点A四周扩散一次，四周走过，恰巧右方是第二个结点B，下方是最后一个结点E，那么以B怎么扩散都不能访问到E，因为E被走过，B怎么走都走不到E，所以个人觉得BFS不能用来解决这道题，只能用DFS一条路走到黑的方式来解决）

这道题就是以矩阵中的每一个点作为为起点去执行一次DFS。而DFS的执行过程就是：

1. 每次执行DFS先判断走过的路径是不是等于要求的路径，是就返回结果true，不是就继续找。
2. 先判断当前点是否可走，不是，则返回上一层；是就顺时针探寻下一个方位的结点（上、右、下、左），以下一个方位结点进行DFS，如果方位都探完了还找不到路径，那么当前节点不可能是路径结点之一，只能返回上一层。

Java代码实现

public class Solution {
    private boolean visited[] = null;//标志每个位置是否走过，true走过，false没走过

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix == null || str == null || str.length > matrix.length || rows * cols != matrix.length)
            //进行非法性判断
            return false;
        //初始化visited数组
        visited = new boolean[rows * cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                //以每个结点作为起始节点去dfs
                if (dfs(matrix, i, j, rows, cols, str, 0))
                    return true;
            }
        }
        //没有找到
        return false;
    }

    /**
     * @param matrix 地图
     * @param x      起点x
     * @param y      起点y
     * @param rows   行数
     * @param cols   列数
     * @param str    所求路径
     * @param len    当前已经找到路径的长度
     * @return
     */
    private boolean dfs(char[] matrix, int x, int y, int rows, int cols, char[] str, int len) {
        if (len >= str.length) {
            //找到要求的路径
            return true;
        } else {
            //路径长度小于要求的长度，还得继续寻找
            if (x >= 0 && x <= rows - 1 && y >= 0 && y <= cols - 1 && visited[x * cols + y] == false && matrix[x * cols + y] == str[len]) {
                //当前结点是路径节点之一
                visited[x * cols + y] = true;//把当前结点的标志位设为true，证明走过了
                //寻找下一方位
                int dict = 0;
                int x1 = 0, y1 = 0;
                while (dict <= 3) {
                    switch (dict) {
                        case 0: x1 = x - 1; y1 = y; break;
                        case 1: x1 = x ; y1 = y + 1; break;
                        case 2: x1 = x + 1; y1 = y; break;
                        case 3: x1 = x ; y1 = y - 1; break;
                    }
                    if(dfs(matrix, x1, y1, rows, cols, str, len + 1))//判断下一个方位能否找到路径
                        return true; //能，直接返回
                    dict ++;//不能，找下一方位
                }
                //不能从当前结点找不到路径，那就回溯，把当前结点标志位设为false
                visited[x * cols + y] = false;
                return false;//返回失败
            } else{
                //当前结点不是要找的路径，直接回溯
                return false;
            }
        }
    }
}