点击刷新
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[0].size(); queue<pair<int,int>> q; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(matrix[i][j] == 0) 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[0]; int new_y = y + dir[1]; if(new_x < 0 || new_x >= matrix.size() || new_y < 0 || new_y >= matrix[0].size() || matrix[new_x][new_y] <= matrix[x][y] + 1) continue; matrix[new_x][new_y] = matrix[x][y] + 1; q.push(make_pair(new_x,new_y)); } } return matrix; } private: vector<vector<int>> dirs{{-1,0},{1,0},{0,-1},{0,1}}; };
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 = 0;i < rooms.size();i++){ for(int j = 0;j < rooms[0].size();j++){ if(rooms[i][j] == 0) 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[0]; int y_new = y + dir[1]; if(x_new < 0 || x_new >= rooms.size() || y_new < 0 || y_new >= rooms[0].size() || rooms[x_new][y_new] < rooms[x][y] + 1) continue; rooms[x_new][y_new] = rooms[x][y] + 1; q.push(make_pair(x_new,y_new)); } } return; } private: vector<vector<int>> dirs{{-1,0},{1,0},{0,-1},{0,1}}; };
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 = 0,m = board.size(),n = board[0].size(); set<vector<vector<int>>> visited; vector<vector<int>> correct{{1,2,3},{4,5,0}}; queue<pair<vector<vector<int>>,vector<int>>> q; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(board[i][j] == 0){ 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 > 0;i--){ int x = q.front().second[0]; int y = q.front().second[1]; 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[0]; int new_y = y + dir[1]; if(new_x < 0 || new_x >= m || new_y < 0 || 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 -1; } private: vector<vector<int>> dirs{{-1,0},{1,0},{0,-1},{0,1}}; };
注意犯的错误：
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[0].size(); int res = INT_MAX,building = 0; vector<vector<int>> dist(m,vector<int>(n,0)); vector<vector<int>> count = dist; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(grid[i][j] == 1){ building++; queue<pair<int,int>> q; vector<vector<bool>> visited(m,vector<bool>(n,false)); q.push(make_pair(i,j)); int pace = 0; while(!q.empty()){ pace++; for(int i = q.size();i > 0;i--){ int x = q.front().first; int y = q.front().second; q.pop(); for(auto dir : dirs){ int new_x = x + dir[0]; int new_y = y + dir[1]; if(new_x < 0 || new_x >= m || new_y < 0 || new_y >= n || visited[new_x][new_y]== true || grid[new_x][new_y] != 0) continue; dist[new_x][new_y] += pace; count[new_x][new_y] += 1; visited[new_x][new_y] = true; q.push(make_pair(new_x,new_y)); } } } } } } for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(grid[i][j] == 0 && count[i][j] == building) res = min(res,dist[i][j]); } } return res == INT_MAX ? -1 : res; } private: vector<vector<int>> dirs{{-1,0},{1,0},{0,-1},{0,1}}; };
另一种写法：
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[0].size(); vector<vector<int> > path(m,vector<int>(n,0)); vector<vector<int> > count(m,vector<int>(n,0)); int building = 0; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(grid[i][j] == 1){ building++; vector<vector<bool> > visited(m,vector<bool>(n,false)); search(grid,i,j,path,count,visited); } } } int res = INT_MAX; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(grid[i][j] == 0 && count[i][j] == building) res = min(res,path[i][j]); } } return res == INT_MAX ? -1 : 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 = 0; while(!q.empty()){ pace++; for(int i = q.size();i > 0;i--){ int x0 = q.front().first; int y0 = q.front().second; q.pop(); //visited[x0][y0] = true; for(int j = 0;j < dirs.size();j++){ int new_x = x0 + dirs[j][0]; int new_y = y0 + dirs[j][1]; if(new_x < 0 || new_x >= path.size() || new_y < 0 || new_y >= path[0].size() || visited[new_x][new_y] || grid[new_x][new_y] != 0) 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{{-1,0},{1,0},{0,-1},{0,1}}; }; //visited[new_x][new_y] = true;只能放在新生成的坐标的位置
© 著作权归作者所有
举报
发表评论
0/200
