(https://leetcode-cn.com/problems/xun-bao/)
思路可以看官方题解，这里只记录一下小的知识点
1.bfs使用不当会导致超时（还是自己菜）当时我想的就是逐层去遍历嘛，于是就在每一层的while循环中让上一层都给吐出来，这样写有个问题（可以看代码），当前刚push进去的点在下一个while循环中才会对res进行赋值，所以说这样写会push进去很多多余的点（还是官方题解写得好）
//超时bfs
vector<vector<int>> bfs(int x,int y){
vector<vector<int>> res(n,vector<int>(m,-1));
queue<pair<int,int>> que;
que.push(MP(x,y));
int ans = -1;
while(!que.empty()){
ans++;
int num = que.size();
for(int k = 1; k <= num; k++){
int now_x = que.front().first,now_y = que.front().second;
que.pop();
res[now_x][now_y] = ans;
for(int i = 0; i < 4; i++){
int cnt_x = now_x+dx[i],cnt_y = now_y+dy[i];
if(isbound(cnt_x,cnt_y) && G[cnt_x][cnt_y] != ‘#‘ && res[cnt_x][cnt_y] == -1){
que.push(MP(cnt_x,cnt_y));
}
}
}
}
return res;
}
//正解bfs
vector<vector<int>> bfs(int x,int y){
vector<vector<int>> res(n,vector<int>(m,-1));
queue<pair<int,int>> que;
que.push(MP(x,y));
res[x][y] = 0;
while(!que.empty()){
int now_x = que.front().first,now_y = que.front().second;
que.pop();
for(int i = 0; i < 4; i++){
int cnt_x = now_x+dx[i],cnt_y = now_y+dy[i];
if(isbound(cnt_x,cnt_y) && G[cnt_x][cnt_y] != ‘#‘ && res[cnt_x][cnt_y] == -1){
que.push(MP(cnt_x,cnt_y));
res[cnt_x][cnt_y] = res[now_x][now_y]+1;
}
}
}
return res;
}
2.求x的第i位二进制：x&(1<<i) ， 这个如果是0,就说明x的二进制的第i位为0。否则就说明x的二进制的第i位不为0（不一定是1），可能隔得时间太长了，也可能是我太**了，我竟然以为当第i位为1的时候，x&(1<<i) 等于1，而且我还想不通为什么....
3.让x的第i位二进制变为0 只需要x-(1<<i)就行了....
4.我做这个题之前是不会状压dp的，当然现在 做过也不一定会，总之就是感觉状压dp很奇妙，和普通的dp有相似点也有不同点，等我有空刷刷状压dp的习题在记录一下感觉
//完整代码
#define MP(x,y) make_pair(x,y)
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
class Solution {
public:
vector<string> G;
int n,m;
bool isbound(int x,int y){
if(x >= 0 && x < n && y >= 0 && y < m) return true;
else return false;
}
vector<vector<int>> bfs(int x,int y){
vector<vector<int>> res(n,vector<int>(m,-1));
queue<pair<int,int>> que;
que.push(MP(x,y));
res[x][y] = 0;
while(!que.empty()){
int now_x = que.front().first,now_y = que.front().second;
que.pop();
for(int i = 0; i < 4; i++){
int cnt_x = now_x+dx[i],cnt_y = now_y+dy[i];
if(isbound(cnt_x,cnt_y) && G[cnt_x][cnt_y] != ‘#‘ && res[cnt_x][cnt_y] == -1){
que.push(MP(cnt_x,cnt_y));
res[cnt_x][cnt_y] = res[now_x][now_y]+1;
}
}
}
return res;
}
int minimalSteps(vector<string>& maze) {
n = maze.size(),m = maze[0].size();
G = maze;
vector<pair<int,int>> btn,stone;
int begin_x,begin_y,end_x,end_y;
int btn_num = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(maze[i][j] == ‘M‘) btn.push_back(MP(i,j)),btn_num++;
if(maze[i][j] == ‘O‘) stone.push_back(MP(i,j));
if(maze[i][j] == ‘S‘) begin_x = i,begin_y = j;
if(maze[i][j] == ‘T‘) end_x = i,end_y = j;
}
}
vector<vector<int>> start_dis = bfs(begin_x,begin_y);
//cout<<1<<endl;
vector<vector<int>> end_dis = bfs(end_x,end_y);
if(btn_num == 0) return start_dis[end_x][end_y];
// for(int i = 0; i < n; i++){
// for(int j = 0; j < m; j++){
// cout<<start_dis[i][j]<<" ";
// }
// cout<<endl;
// }
// for(int i = 0; i < n; i++){
// for(int j = 0; j < m; j++){
// cout<<end_dis[i][j]<<" ";
// }
// cout<<endl;
// }
vector<vector<vector<int>>> d;//以每个机关为起点遍历出来得距离
btn.push_back(MP(begin_x,begin_y));
for(int i = 0; i < btn.size(); i++){
d.push_back(bfs(btn[i].first,btn[i].second));
}
vector<vector<int>> pre_dist(btn.size(),vector<int>(stone.size(),-1));
//求得每个btn与石堆之间得距离
for(int i = 0; i < btn.size(); i++){
for(int j = 0; j < stone.size(); j++){
pre_dist[i][j] = d[i][stone[j].first][stone[j].second];
}
}
//求btn与btnx 之间经过一个石堆得最短距离
vector<vector<int>> dist(btn.size(),vector<int>(btn.size(),-1));
for(int i = 0; i < btn.size(); i++){
for(int j = 0; j < btn.size(); j++){
if(i == j) continue;
for(int k = 0; k < stone.size(); k++){
if(pre_dist[i][k] == -1 || pre_dist[j][k] == -1) continue;
if(dist[i][j] < 0) dist[i][j] = pre_dist[i][k]+pre_dist[j][k];
else dist[i][j] = min(dist[i][j],pre_dist[i][k]+pre_dist[j][k]);
}
}
}
// for(int i = 0; i < btn_num; i++){
// cout<<dist[i][btn_num]<<" ";
// }
//特判
for(int i = 0; i < btn_num; i++){
int x = btn[i].first,y = btn[i].second;
if(end_dis[x][y] < 0 || dist[i][btn_num] < 0) return -1;
}
//dp过程
int state = 1<<btn_num;
vector<vector<int>> dp(state,vector<int>(btn_num,-1));
for(int i = 0; i < btn_num; i++){//初始化
dp[1 << i][i] = dist[btn_num][i];
}
for(int i = 1; i < state; i++){
for(int j = 0; j < btn_num; j++){
if(i & (1<<j)){
for(int k = 0; k < btn_num; k++){
if(i & (1<<k)){
if(dp[i-(1<<j)][k] < 0 || dist[j][k] < 0) continue;
if(dp[i][j] == -1) dp[i][j] = dp[i-(1<<j)][k]+dist[j][k];
else dp[i][j] = min(dp[i][j],dp[i-(1<<j)][k]+dist[j][k]);
}
}
}
}
}
// for(int i = 0; i < btn_num; i++){
// for(int j = 1; j < state; j++){
// cout<<dp[j][i]<<" ";
// }
// cout<<endl;
// }
int ans = dp[state-1][0]+end_dis[btn[0].first][btn[0].second];
for(int i = 1; i < btn_num; i++){
//cout<<i<<endl;
//cout<<btn[i].first<<" "<<btn[i].second<<endl;
ans = min(ans,dp[state-1][i]+end_dis[btn[i].first][btn[i].second]);
}
return ans;
}
};
原文：https://www.cnblogs.com/Beic233/p/13401540.html