leetcode 542. 01 Matrix 、663. Walls and Gates(lintcode) 、773. Sliding Puzzle 、803. Shortest Distance from All Buildings

542. 01 Matrix

https://www.cnblogs.com/grandyang/p/6602288.html

将所有的1置为INT_MAX，然后用所有的0去更新原本位置为1的值。

最短距离肯定使用bfs。

每次更新了值的地方还要再加入队列中。

class Solution {

public:

    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

        int m = matrix.size(),n = matrix[].size();

        queue<pair<int,int>> q;

        for(int i = ;i < m;i++){

            for(int j = ;j < n;j++){

                if(matrix[i][j] == )

                    q.push(make_pair(i,j));

                else

                    matrix[i][j] = INT_MAX;

            }

        }

        while(!q.empty()){

            auto coordinate = q.front();

            q.pop();

            int x = coordinate.first,y = coordinate.second;

            for(auto dir : dirs){

                int new_x = x + dir[];

                int new_y = y + dir[];

                if(new_x <  || new_x >= matrix.size() || new_y <  || new_y >= matrix[].size() || matrix[new_x][new_y] <= matrix[x][y] + )

                    continue;

                matrix[new_x][new_y] = matrix[x][y] + ;

                q.push(make_pair(new_x,new_y));

            }

        }

        return matrix;

    }

private:

    vector<vector<int>> dirs{{-,},{,},{,-},{,}};

};

663. Walls and Gates

https://www.cnblogs.com/grandyang/p/5285868.html

这个题跟542. 01 Matrix很像，主要利用bfs。先把所有的0位置放入队列中，然后通过0更新周围的位置达到更新所有的位置。

class Solution {

public:

    /**

     * @param rooms: m x n 2D grid

     * @return: nothing

     */

    void wallsAndGates(vector<vector<int>> &rooms) {

        // write your code here

        queue<pair<int,int>> q;

        for(int i = ;i < rooms.size();i++){

            for(int j = ;j < rooms[].size();j++){

                if(rooms[i][j] == )

                    q.push(make_pair(i,j));

            }

        }

        while(!q.empty()){

            int x = q.front().first;

            int y = q.front().second;

            q.pop();

            for(auto dir : dirs){

                int x_new = x + dir[];

                int y_new = y + dir[];

                if(x_new <  || x_new >= rooms.size() || y_new <  || y_new >= rooms[].size() || rooms[x_new][y_new] < rooms[x][y] + )

                    continue;

                rooms[x_new][y_new] = rooms[x][y] + ;

                q.push(make_pair(x_new,y_new));

            }

        }

        return;

    }

private:

    vector<vector<int>> dirs{{-,},{,},{,-},{,}};

};

773. Sliding Puzzle

https://www.cnblogs.com/grandyang/p/8955735.html

queue里面存储的是每次变换后的board的样子和当前新的board中0所在的坐标。

将队列一次清空完了之后才能更新res，因为这就是一次变换。

用set相当于决定什么时候停止循环

class Solution {

public:

    int slidingPuzzle(vector<vector<int>>& board) {

        int res = ,m = board.size(),n = board[].size();

        set<vector<vector<int>>> visited;

        vector<vector<int>> correct{{,,},{,,}};

        queue<pair<vector<vector<int>>,vector<int>>> q;

        for(int i = ;i < m;i++){

            for(int j = ;j < n;j++){

                if(board[i][j] == ){

                    vector<int> tmp;

                    tmp.push_back(i);

                    tmp.push_back(j);

                    q.push(make_pair(board,tmp));

                }

            }

        }

        while(!q.empty()){

            for(int i = q.size();i > ;i--){

                int x = q.front().second[];

                int y = q.front().second[];

                vector<vector<int>> board_new = q.front().first;

                if(board_new == correct)

                    return res;

                visited.insert(board_new);

                q.pop();

                for(auto dir : dirs){

                    int new_x = x + dir[];

                    int new_y = y + dir[];

                    if(new_x <  || new_x >= m || new_y <  || new_y >= n)

                        continue;

                    vector<vector<int>> cand = board_new;

                    swap(cand[x][y],cand[new_x][new_y]);

                    if(visited.find(cand) != visited.end())

                        continue;

                    vector<int> tmp;

                    tmp.push_back(new_x);

                    tmp.push_back(new_y);

                    q.push(make_pair(cand,tmp));

                }

            }

            res++;

        }

        return -;

    }

private:

    vector<vector<int>> dirs{{-,},{,},{,-},{,}};

};

注意犯的错误：

for(int i = q.size();i > 0;i--)不能写成for(int i = 0;i < q.size();i++)，因为q的size在循环一次后，大小是缩小的，这样不能保证正确的次数。

803. Shortest Distance from All Buildings

https://www.cnblogs.com/grandyang/p/5297683.html

到所有建筑物的距离和最小，其实也就等于到每个建筑物最小距离的和。

以每个建筑物做bfs求最小的距离，然后用一个dis的vector保存，每当增加一个建筑物，在相应位置叠加当前建筑物的最小距离即可。

有可能有些点无法访问到某一些建筑物，所以通过一个count矩阵存储每个位置能访问到的建筑物的个数，最后再判断能否达到。

class Solution {

public:

    /**

     * @param grid: the 2D grid

     * @return: the shortest distance

     */

    int shortestDistance(vector<vector<int>> &grid) {

        // write your code here

        int m = grid.size(),n = grid[].size();

        int res = INT_MAX,building = ;

        vector<vector<int>> dist(m,vector<int>(n,));

        vector<vector<int>> count = dist;

        for(int i = ;i < m;i++){

            for(int j = ;j < n;j++){

                if(grid[i][j] == ){

                    building++;

                    queue<pair<int,int>> q;

                    vector<vector<bool>> visited(m,vector<bool>(n,false));

                    q.push(make_pair(i,j));

                    int pace = ;

                    while(!q.empty()){

                        pace++;

                        for(int i = q.size();i > ;i--){

                            int x = q.front().first;

                            int y = q.front().second;

                            q.pop();

                            for(auto dir : dirs){

                                int new_x = x + dir[];

                                int new_y = y + dir[];

                                if(new_x <  || new_x >= m || new_y <  || new_y >= n || visited[new_x][new_y]== true || grid[new_x][new_y] != )

                                    continue;

                                dist[new_x][new_y] += pace;

                                count[new_x][new_y] += ;

                                visited[new_x][new_y] = true;

                                q.push(make_pair(new_x,new_y));

                            }

                        }

                    }

                }

            }

        }

        for(int i = ;i < m;i++){

            for(int j = ;j < n;j++){

                if(grid[i][j] ==  && count[i][j] == building)

                    res = min(res,dist[i][j]);

            }

        }

        return res == INT_MAX ? - : res;

    }

private:

    vector<vector<int>> dirs{{-,},{,},{,-},{,}};

};

另一种写法：

class Solution {

public:

    /**

     * @param grid: the 2D grid

     * @return: the shortest distance

     */

    int shortestDistance(vector<vector<int> > &grid) {

        // write your code here

        int m = grid.size(),n = grid[].size();

        vector<vector<int> > path(m,vector<int>(n,));

        vector<vector<int> > count(m,vector<int>(n,));

        int building = ;

        for(int i = ;i < m;i++){

            for(int j = ;j < n;j++){

                if(grid[i][j] == ){

                    building++;

                    vector<vector<bool> > visited(m,vector<bool>(n,false));

                    search(grid,i,j,path,count,visited);

                }

            }

        }

        int res = INT_MAX;

        for(int i = ;i < m;i++){

            for(int j = ;j < n;j++){

                if(grid[i][j] ==  && count[i][j] == building)

                    res = min(res,path[i][j]);

            }

        }

        return res == INT_MAX ? - : res;

    }

    void search(vector<vector<int> > grid,int x,int y,vector<vector<int> >& path,vector<vector<int> >& count,vector<vector<bool> > visited){

        queue<pair<int,int> > q;

        q.push(make_pair(x,y));

        int pace = ;

        while(!q.empty()){

            pace++;

            for(int i = q.size();i > ;i--){

                int x0 = q.front().first;

                int y0 = q.front().second;

                q.pop();

                //visited[x0][y0] = true;

                for(int j = ;j < dirs.size();j++){

                    int new_x = x0 + dirs[j][];

                    int new_y = y0 + dirs[j][];

                    if(new_x <  || new_x >= path.size() || new_y <  || new_y >= path[].size() || visited[new_x][new_y] || grid[new_x][new_y] != )

                        continue;

                    path[new_x][new_y] += pace;

                    count[new_x][new_y]++;

                    visited[new_x][new_y] = true;

                    q.push(make_pair(new_x,new_y));

                }

            }

        }

    }

private:

    vector<vector<int> > dirs{{-,},{,},{,-},{,}};

};

//visited[new_x][new_y] = true;只能放在新生成的坐标的位置

巴特西

leetcode 542. 01 Matrix 、663. Walls and Gates(lintcode) 、773. Sliding Puzzle 、803. Shortest Distance from All Buildings

最新文章

热门文章