LeetCode.1091.130.797(广度优先搜索&深度优先搜索)

今天的题目真滴难，一天都花在这上面，JAVA都没碰

1091.二进制矩阵中的最短路径

class Solution {
  public:
    /* int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1)
                    grid[i][j] = 0;
                else
                    grid[i][j] = INT_MAX;
            }
        }
        if (grid[0][0] == 0 || grid[grid.size() - 1][grid[0].size() - 1] == 0)
            return -1;
        grid[0][0] = 1;
        find(grid, 0, 0);
        return grid[grid.size() - 1][grid[0].size() - 1] == INT_MAX ? -1 : grid[grid.size() - 1][grid[0].size() - 1];
    }
    void find(vector<vector<int>> &grid, int startX, int startY) {
        int nextX[8] = {1, 1, 0, 1, -1, -1, 0, -1};
        int nextY[8] = {1, 0, 1, -1, 1, 0, -1, -1};
        int minPath = INT_MAX;
        for (int i = 0; i < 8; i++) {
            if (startX + nextX[i] < 0 || startX + nextX[i] > grid[0].size() - 1 || startY + nextY[i] < 0 ||
                startY + nextY[i] > grid.size() - 1 || grid[startY + nextY[i]][startX + nextX[i]] == 0 ||
                grid[startY + nextY[i]][startX + nextX[i]] <= grid[startY][startX]) {
                continue;
            }
            grid[startY + nextY[i]][startX + nextX[i]] = grid[startY][startX] + 1;
            find(grid, startX + nextX[i], startY + nextY[i]);
        }
    }
    超时,深搜不行 */
    int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
        int n = grid.size();
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1)
            return -1;
        int length = 1;
        queue<int> q;
        grid[0][0] = 1;
        q.push(0);
        int dirX[8] = {0, 0, 1, -1, 1, 1, -1, -1};
        int dirY[8] = {1, -1, 0, 0, 1, -1, 1, -1};
        while (!q.empty()) {
            int qSize = q.size();
            for (int i = 0; i < qSize; i++) {
                int x = q.front() % n;
                int y = q.front() / n;
                q.pop();
                if (x == n - 1 && y == n - 1)
                    return length;
                for (int i = 0; i < 8; i++) {
                    if (x + dirX[i] < 0 || x + dirX[i] > n - 1 || y + dirY[i] < 0 || y + dirY[i] > n - 1 ||
                        grid[x + dirX[i]][y + dirY[i]])
                        continue;
                    grid[x + dirX[i]][y + dirY[i]] = 1;
                    q.push((y + dirY[i]) * n + x + dirX[i]);
                }
            }
            length++;
        }
        return -1;
    }
    // 88/88 cases passed (48 ms)
    // Your runtime beats 82.33 % of cpp submissions
    // Your memory usage beats 97.2 % of cpp submissions (17.8 MB)
    //*广搜还能一组一组来的啊，见识到了
};

130.被围绕的区域

class Solution {
  public:
    int dirX[4] = {1, 0, -1, 0};
    int dirY[4] = {0, 1, 0, -1};
    vector<vector<bool>> mark;
    /* void solve(vector<vector<char>> &board) {
        for (int i = 0; i < board.size(); i++) {
            if (board[i][board[0].size() - 1] == 'O') {
                fill(board, board[0].size() - 1, i, 'A');
            }
            if (board[i][0] == 'O') {
                fill(board, 0, i, 'A');
            }
        }
        for (int i = 0; i < board[0].size(); i++) {
            if (board[board.size() - 1][i] == 'O') {
                fill(board, i, board.size() - 1, 'A');
            }
            if (board[0][i] == 'O') {
                fill(board, i, 0, 'A');
            }
        }
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == 'O') {
                    fill(board, j, i, 'X');
                }
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    void fill(vector<vector<char>> &board, int x, int y, char target) {
        if (x < 0 || x >= board[0].size() || y < 0 || y >= board.size() || board[y][x] != 'O')
            return;
        board[y][x] = target;
        for (int i = 0; i < 4; i++) {
            fill(board, x + dirX[i], y + dirY[i], target);
        }
    } */
    // 58/58 cases passed (8 ms)
    // Your runtime beats 95.17 % of cpp submissions
    // Your memory usage beats 10.46 % of cpp submissions (12.6 MB)
    void solve(vector<vector<char>> &board) {
        mark = vector<vector<bool>>(board.size(), vector<bool>(board[0].size(), 0));
        for (int i = 0; i < board.size(); i++) {
            if (board[i][board[0].size() - 1] == 'O') {
                search(board, board[0].size() - 1, i);
            }
            if (board[i][0] == 'O') {
                search(board, 0, i);
            }
        }
        for (int i = 0; i < board[0].size(); i++) {
            if (board[board.size() - 1][i] == 'O') {
                search(board, i, board.size() - 1);
            }
            if (board[0][i] == 'O') {
                search(board, i, 0);
            }
        }
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == 'O' && !mark[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }
    void search(vector<vector<char>> &board, int x, int y) {
        if (x < 0 || x >= board[0].size() || y < 0 || y >= board.size() || board[y][x] != 'O' || mark[y][x])
            return;
        mark[y][x] = 1;
        for (int i = 0; i < 4; i++) {
            search(board, x + dirX[i], y + dirY[i]);
        }
    }
    // 58/58 cases passed (4 ms)
    // Your runtime beats 99.9 % of cpp submissions
    // Your memory usage beats 58.12 % of cpp submissions (9.8 MB)
    //*用堆空间换栈空间
};

797.所有可能的路径

class Solution {
  public:
    /* vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
        int n = graph.size();
        if (graph.size() <= 1 || graph[0].empty())
            return {};
        queue<vector<int>> q;
        for (int i = 0; i < graph[0].size(); i++) {
            q.push({0, graph[0][i]});
        }
        vector<vector<int>> path;
        while (!q.empty()) {
            vector<int> temp = q.front();
            q.pop();
            if (temp.back() == n - 1) {
                path.push_back(temp);
                continue;
            }
            if (graph[temp.back()].empty()) {
                continue;
            } else {
                for (int i = 0; i < graph[temp.back()].size(); i++) {
                    temp.push_back(graph[temp.back()][i]);
                    q.push(temp);
                    temp.pop_back();
                }
            }
        }
        return path;
        // 30/30 cases passed (28 ms)
        // Your runtime beats 15.15 % of cpp submissions
        // Your memory usage beats 13.31 % of cpp submissions (16.2 MB)
        //BFS
    } */

    /* vector<vector<int>> path;
    vector<vector<int>> ans;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
        if (graph.size() <= 1 || graph[0].empty())
            return {};
        for (int i = 0; i < graph[0].size(); i++) {
            path.push_back({0, graph[0][i]});
            dfs(graph);
        }
        return ans;
    }
    void dfs(vector<vector<int>> &graph) {
        auto temp = path.back();
        path.pop_back();
        if (temp.back() == graph.size() - 1) {
            ans.push_back(temp);
            return;
        }
        if (graph[temp.back()].empty()) {
            return;
        }
        for (int i = 0; i < graph[temp.back()].size(); i++) {
            temp.push_back(graph[temp.back()][i]);
            path.push_back(temp);
            dfs(graph);
            temp.pop_back();
        }
    }
    // 30/30 cases passed (32 ms)
    // Your runtime beats 9.92 % of cpp submissions
    // Your memory usage beats 8.87 % of cpp submissions (17 MB)
    //*咋更慢？？？
    //全局变量影响效率
     */
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
        vector<int> arr{0};
        vector<vector<int>> ans;
        func(graph, ans, arr, 0, graph.size() - 1);
        return ans;
    }
    void func(vector<vector<int>> &graph, vector<vector<int>> &ans, vector<int> &arr, int s, int e) {
        if (s == e) {
            ans.push_back(arr);
            return;
        }
        for (auto &i : graph[s]) {
            arr.push_back(i);
            func(graph, ans, arr, i, e);
            arr.pop_back();
        }
    }
    // 30/30 cases passed (8 ms)
    // Your runtime beats 96.08 % of cpp submissions
    // Your memory usage beats 94.2 % of cpp submissions (10.3 MB)
    //我累个乖乖
};