矩阵中路径

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

    public int res = 0;
    public int[][] position = new int[][]{{-1,0}, {1,0}, {0,-1},{0,1}};
    public int movingCount(int threshold, int rows, int cols)
    {
        boolean[][] visited = new boolean[rows][cols];
        dfs(0,0, rows, cols, visited, threshold);
        return res;
    }
    
    private void dfs(int row, int col, int rows, int cols, boolean[][] visited, int threshold) {
        if(row < 0 || col < 0 || row >= rows || col >= cols || visited[row][col] || countSum(row, col, threshold)) {
            return;
        }
        res++;
        visited[row][col] = true;
        for(int[] pos : position) {
            dfs(row + pos[0], col + pos[1], rows, cols, visited, threshold);
        }    
    }
    
    private boolean countSum(int row, int col, int threshold) {
        int res = 0;
        while(row != 0) {
            res += row % 10;
            row = row / 10;
        }
        while(col != 0) {
            res += col % 10;
            col /= 10;
        }
        return res > threshold;
    }
}

• C++ 代码

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        int count = 0;
        bool *visited = new bool[rows*cols];
        memset(visited, 0 , rows*cols);
        count = dfs(threshold, rows, cols, 0, 0,  visited);
        delete[] visited;
        return count;
    }
    int dfs(int threshold, int rows, int cols,int i, int j, bool *visited){
        if(i<0||j<0||i>=rows||j>=cols||!isEnter(threshold,i,j)) return 0;
        if(!visited[i*cols+j]){
            visited[i*cols+j] = true;
            return 1+dfs(threshold, rows, cols, i-1, j,  visited) + dfs(threshold, rows, cols, i+1, j,  visited)
                    +dfs(threshold, rows, cols, i, j-1,  visited) + dfs(threshold, rows, cols, i, j+1,  visited);
        }
        return 0;
    }
    bool isEnter(int threshold,int i, int j){
        int sum = 0;
        while(i){
            sum += i%10;
            i = i/10;
        }
        while(j){
            sum += j%10;
            j = j/10;
        }
        if(sum>threshold) return false;
        return true;
    }
};