leetcode bizarre BFS (529, 417, 1162, 752, 909)

529 Minesweeper

Topic Description: given a two-dimensional character matrix representing the game board. 'M' stands for an unearthed mine, 'E' stands for an unearthed empty square, 'B' stands for an unearthed empty square without adjacent mines (top, bottom, left, right, and all four diagonals), the numbers ('1 'to' 8 ') stand for how many mines are adjacent to the excavated square,' X 'stands for an excavated mine.

Now, the next click position (row and column index) in all unearthed blocks ('M' or 'E') is given. According to the following rules, the corresponding panel after the corresponding position is clicked is returned:

  1. If a mine ('M ') is dug out, the game is over - change it to' X '.
  2. If an empty square ('E ') without adjacent mines is dug out, change it to ('B') and all adjacent squares should be exposed recursively.
  3. If an empty square ('E ') adjacent to at least one mine is excavated, change it to a number ('1' to '8') to indicate the number of adjacent mines.
  4. If there are no more squares to be revealed in this click, return to the panel.

Thinking: BFS. It is required to count whether there are bombs in eight directions around each position pushed into the queue. If there are bombs, the value of this position will change to the number of bombs around, and this point will no longer be pushed into the queue to continue BFS. Only when the surrounding bomb is zero, the location is pressed into the queue and the search continues. When setting the vis [] [] array and counting the number of bombs around, it is not necessary to consider whether the point has been traversed (pushed into the queue). When pressing into the queue, it is necessary to consider.

class Solution {
public:
    struct point{
        int x, y;
    };
    int dir[8][2] = {1,0,-1,0,0,1,0,-1,-1,-1,1,1,-1,1,1,-1};
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int n = board.size(), m = board[0].size();
        if(board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
            //cout<<"11111111"<<endl;
            return board;
        }
        queue<point> Q;
        vector<vector<int>> vis(n, vector<int>(m, 0));
        Q.push(point{click[0], click[1]});
        vis[click[0]][click[1]] = 1;
        while(!Q.empty()) {
            point q = Q.front();
            Q.pop();
            int cnt = 0;
            for(int i = 0; i < 8; i++) {
                int x = q.x + dir[i][0];
                int y = q.y + dir[i][1];
                if(x >= 0 && x < n && y >= 0 && y < m && board[x][y] == 'M')
                    cnt++;
            }
            if(cnt == 0) {
                board[q.x][q.y] = 'B';
                for(int i = 0; i < 8; i++) {
                    int x = q.x + dir[i][0];
                    int y = q.y + dir[i][1];
                    if(x >= 0 && x < n && y >= 0 && y < m && vis[x][y] == 0){
                        Q.push(point{x, y});
                        vis[x][y] = 1;
                    }
                       
                }
            }
            else
                board[q.x][q.y] = ('0' + cnt);
        }
        return board;
    }
};

417 Pacific Atlantic current problems

Topic Description: a nonnegative integer matrix of m x n is given to represent the height of each cell in a continent. The Pacific Ocean is on the left and the upper boundary of the continent, while the Atlantic Ocean is on the right and the lower boundary of the continent. It is specified that water flow can only flow in the up, down, left and right directions, and can only flow from high to low or at the same height.
Please find out the coordinates of land units that can flow to both the Pacific Ocean and the Atlantic Ocean.
Tip: the order of output coordinates is not important; m and n are less than 150.
Idea: BFS reverse diffusion. Start countercurrent from two oceans, Mark 1 if you can countercurrent to, and then check the area that both oceans can countercurrent to.

class Solution {
public:
    struct point {
        int x, y; 
    };
    int dir[4][2] = {1,0,-1,0,0,1,0,-1};
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<int>> ans;
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return ans;
        int n = matrix.size(), m = matrix[0].size();
        queue<point> Q1, Q2;
        vector<vector<int>> vis1(n, vector<int>(m, 0));
        vector<vector<int>> vis2(n, vector<int>(m, 0));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(i == 0 || j == 0) {
                    Q1.push(point{i, j});
                    vis1[i][j] = 1;
                }  
                if(i == n - 1 || j == m - 1){
                    Q2.push(point{i, j});
                    vis2[i][j] = 1;
                }   
            }
        }
        while(!Q1.empty()) {
            point q = Q1.front();
            Q1.pop();
            for(int i = 0; i < 4; i++) {
                int x = q.x + dir[i][0];
                int y = q.y + dir[i][1];
                if(x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] >= matrix[q.x][q.y] && vis1[x][y] == 0) {
                    Q1.push(point{x, y});
                    vis1[x][y] = 1;
                }
            }
        }
        while(!Q2.empty()) {
            point q = Q2.front();
            Q2.pop();
            for(int i = 0; i < 4; i++) {
                int x = q.x + dir[i][0];
                int y = q.y + dir[i][1];
                if(x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] >= matrix[q.x][q.y] && vis2[x][y] == 0) {
                    Q2.push(point{x, y});
                    vis2[x][y] = 1;
                }
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(vis1[i][j] == 1 && vis2[i][j] == 1) {
                    vector<int> tmp(2, 0);
                    tmp[0] = i;
                    tmp[1] = j;
                    ans.push_back(tmp);
                }
            }
        }
        return ans;
    }
};

1162 map analysis

Title Description: you have a map (grid) grid with the size of N x N. each area (cell) above is marked with 0 and 1. Among them, 0 represents the ocean, 1 represents the land. Do you know which ocean area is the farthest from the land area? Please return to the distance from the ocean area to the nearest land area.
The distance we are talking about here is "Manhattan Distance": (x0, y0) and (x1, y1) the distance between these two areas is x0 - x1| + |y0 - y1|.
If there is only land or sea on our map, please return to - 1.
Thinking: BFS. Using the distance array dis [] [] to represent the Manhattan distance of all points from the land, the Manhattan distance of the original land point is 0, and the Manhattan distance of the ocean is initialized to - 1. Start from all the land, and then start the BFS type diffusion from the land, and then add one counter (Manhattan distance) for each diffusion layer, and continue "land reclamation" until the whole map no longer has the ocean, and update the counter every time, and update the value of the maximum Manhattan distance at the same time, and finally return the maximum value.

class Solution {
public:
    struct point {
        int x, y;
    };
    int dir[4][2] = {1,0,-1,0,0,1,0,-1};
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dis(n, vector<int>(m, -1));
        queue<point> Q;
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 1) {
                    Q.push(point{i, j});
                    dis[i][j] = 0;
                    cnt++;
                }
            }
        }
        if(cnt == 0 || cnt == n * m)
            return -1;
        
        int ans = 0;
        while(!Q.empty()) {
            point q = Q.front();
            Q.pop();
            for(int i = 0; i < 4; i++) {
                int x = q.x + dir[i][0];
                int y = q.y + dir[i][1];
                if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0 && dis[x][y] == -1) {
                    dis[x][y] = dis[q.x][q.y] + 1;
                    ans = max(ans, dis[x][y]);
                    Q.push(point{x, y});
                }
            }
        }
        return ans;
    }
};

752 open turntable lock

Title Description: you have a turntable lock with four round dials. Each wheel has 10 numbers: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Each wheel can rotate freely: for example, change "9" to "0" and "0" to "9". Each rotation can only rotate one digit of a wheel.
The initial number of the lock is' 0000 ', a string representing the number of four dials.
The list deadends contains a set of death numbers. Once the number of the dial wheel is the same as any element in the list, the lock will be permanently locked and can no longer be rotated.
The string target represents the number that can be unlocked. You need to give the minimum number of rotations. If you can't unlock anyway, return - 1.
Thinking: BFS. The shortest path refers to the minimum number of transformations required to convert the starting state "0000" to the target state, so BFS can be used to solve this kind of shortest path problem. First of all, the death numbers in the deadends are stored in the unordered_map, and their values are mapped to 1, which is convenient to find out whether the resulting state exists in the deadends. For each state, it can expand to up to eight states, that is, its i = 0, 1, 2, 3 bits can be increased by 1 or decreased by 1, all the states that have not been searched and are not in the deadends are added to the queue, and the search continues.

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_map<string, int> mp;
        for(int i = 0; i < deadends.size(); i++) {
            mp[deadends[i]] = 1;
        }
        queue<string> Q;
        unordered_map<string, int> vis;
        unordered_map<string, int> dis;
        if(mp["0000"] == 1)
            return -1;
        Q.push("0000");
        vis["0000"] = 1;
        while(!Q.empty()) {
            string q = Q.front();
            Q.pop();
            if(q == target)
                return dis[q];
            for(int i = 0; i < 4; i++) {
                string tmp1 = q, tmp2 = q;
                if(q[i] == '9') {
                    tmp1[i] = '0';
                    tmp2[i] = '8'; 
                }
                else if(q[i] == '0') {
                    tmp1[i] = '1';
                    tmp2[i] = '9';                    
                }
                else {
                    tmp1[i] += 1;
                    tmp2[i] -= 1;
                }
                if(mp[tmp1] == 0 && vis[tmp1] == 0) {
                    Q.push(tmp1);
                    vis[tmp1] = 1;
                    dis[tmp1] = dis[q] + 1;
                }
                if(mp[tmp2] == 0 && vis[tmp2] == 0) {
                    Q.push(tmp2);
                    vis[tmp2] = 1;
                    dis[tmp2] = dis[q] + 1;
                }
            }
        }
        return -1;
    }
};

909 snake ladder

Title Description: on an N x N board, starting from the lower left corner of the board, each line alternates directions, and numbers the squares from 1 to N * N. Players start from grid 1 (always in the last row, first column) on the board. Each movement from grid x consists of the following parts:
You select a target block S, whose number is x+1, x+2, x+3, x+4, x+5, or x+6, as long as the number is < = n * n.
If S has a snake or ladder, you move to the destination of that snake or ladder. Otherwise, you will move to S.
There is "snake" or "ladder" in the box on column c of row r; if board[r][c]! = - 1, the destination of the snake or ladder will be board[r][c].
Note that you can only climb a snake or ladder once at a time: even if the destination is the starting point of another snake or ladder, you will not continue to move.
Returns the minimum number of moves required to reach square N*N, or - 1 if not possible.
Idea: convert two-dimensional to one-dimensional to avoid calculating coordinates. See change() function. BFS is then used to calculate the minimum number of moves (i.e. the minimum distance).

class Solution {
public:
    void change(vector<vector<int>>& board, vector<int>& vpn, int N) {
        int num = 1, x = 0, y = N - 1;
        int dir = 1; // dir == 1 is from left to right, and dir== -1 is from right to left.
        while(num <= N * N) {
            vpn[num] = board[y][x];
            num++;
            if(dir == 1 && x == N - 1) {
                dir = -1;
                y--;
            }
            else if(dir == -1 && x == 0){
                dir = 1;
                y--;
            }
            else
                x += dir;
        }
        return ;
    }
    int snakesAndLadders(vector<vector<int>>& board) {
        int N = board.size();
        vector<int> dis(N * N + 1, -1);
        vector<int> vpn(N *N + 1, 0);
        change(board, vpn, N);
        queue<int> Q;
        Q.push(1);
        dis[1] = 0;
        while(!Q.empty()) {
            int q = Q.front();
            Q.pop();
            for(int i = 1; i <= 6; i++) {
                int pp = q + i;
                if(pp > N * N)
                    continue;
                if(vpn[pp] != -1) 
                    pp = vpn[pp];
                if(dis[pp] != -1)
                    continue;
                dis[pp] = dis[q] + 1;
                Q.push(pp);
            }
        }
        return dis[N * N];
    }
};
Published 10 original articles, praised 0, visited 21
Private letter follow

Tags: VPN less

Posted on Mon, 13 Jan 2020 20:52:30 -0800 by php_dave