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;只能放在新生成的坐标的位置