1.多源BFS
矩阵距离
就像flood fill 一样，令1的位置距离为0，然后让他来更新其他点的距离
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; #define x first #define y second const int N=1e3+10; int n,m; char g[N][N]; int dist[N][N]; pii q[N*N]; int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; void bfs() { int hh=0,tt=-1; memset(dist,-1,sizeof dist); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j]=='1')//字符为1的点距离为0，并把其入队 { dist[i][j]=0; q[++tt]={i,j}; } while(hh<=tt) { pii t=q[hh++]; for(int i=0;i<4;i++)//覆盖四个方向 { int x=t.x+dx[i],y=t.y+dy[i]; if(dist[x][y]!=-1) continue;//假如之前覆盖过，则不用再次更新 if(x<0||x>=n||y<0||y>=m) continue;//假如越界 dist[x][y]=dist[t.x][t.y]+1; q[++tt]={x,y}; } } } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",g[i]); bfs(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) printf("%d ",dist[i][j]); puts(""); } return 0; }
2.最小步数模型
魔板
#include<bits/stdc++.h> using namespace std; int g[2][4]; unordered_map<string,int> dist; unordered_map<string,pair<char,string>> pre; queue<string> q; string temp; string move0(string m)//第一个操作的变换 { string ans; for(int i=7;i>=0;i--) ans+=m[i]; return ans; } string move1(string m)//第二个操作的变换 { string ans; ans+=m[3]; for(int i=0;i<3;i++) ans+=m[i]; ans+=m[5]; for(int i=6;i<8;i++) ans+=m[i]; ans+=m[4]; return ans; } string move2(string m)//第三个操作的变换 { string ans; ans+=m[0]; ans+=m[6]; ans+=m[1]; ans+=m[3]; ans+=m[4]; ans+=m[2]; ans+=m[5]; ans+=m[7]; return ans; } void bfs(string start,string end) { if(start==end) return;//假如已经是了，则不用操作 q.push(start);//把初始情况放进队列中 dist[start]=0;//初始化距离为0 while(q.size())//当队列不为空 { auto t=q.front();//取出队头 q.pop();//弹出队头 string m[3];//分别进行的三个操作得到的字符串的结果 m[0]=move0(t);//第一个A操作 m[1]=move1(t);//第二个B操作 m[2]=move2(t);//第三个C操作 for(int i=0;i<3;i++) { string temp=m[i]; if(dist.count(temp)==0)//假如改字符串没操作过 { dist[temp]=dist[t]+1;//距离加1 pre[temp]={char(i+'A'),t};//路径存下来 if(temp==end) break;//假如已经搜到了末尾，则退出 q.push(temp); } } } } int main() { int x; string start,end; for(int i=0;i<8;i++)//将读入进行转换成字符串 { cin>>x; end+=char(x+'0'); } for(int i=1;i<=8;i++) start+=char(i+'0');//将初始进行转换字符串 bfs(start,end); cout<<dist[end]<<" ";//输出最小距离 string ans; auto t=end; while(t!=start)//从尾开始往回搜 { ans+=pre[t].first; t=pre[t].second; } reverse(ans.begin(),ans.end());//调转头尾 cout<<ans; return 0; }
3.双端队列广搜（权值只有0和1的时候）
电路维修
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; #define x first #define y second const int N=510; int n,m; char g[N][N]; int dist[N][N]; bool st[N][N]; int bfs() { deque<pii> q;//双端队列 memset(st,0,sizeof st);//清空状态 memset(dist,0x3f,sizeof dist);//清空距离 char cs[5]="\\/\\/";//四个标准方向\/\/,用来比较地图上的方向是否一致 int dx[4]={-1,-1,1,1},dy[4]={-1,1,1,-1};//转换的方向，\/\/ int ix[4]={-1,-1,0,0},iy[4]={-1,0,0,-1};//对应地图的坐标的\/\/ dist[0][0]=0; q.push_back({0,0}); while(q.size()) { auto t=q.front(); q.pop_front(); int x=t.x,y=t.y; if(x==n&&y==m) return dist[x][y];//假如已经搜到n,m了，直接返回 if(st[x][y]) continue;//假如之前已经被搜过了 st[x][y]=true;//标记这个点已经搜过 for(int i=0;i<4;i++)//四个方向进行转移 { int a=x+dx[i],b=y+dy[i];//对应坐标的四个方向 if(a<0||a>n||b<0||b>m) continue;//假如越界 int ga=x+ix[i],gb=y+iy[i];//对应地图的四个方向 int w=g[ga][gb]!=cs[i];//看原图是否跟我转移的方向一致，是则为0，反正为1 int d=dist[x][y]+w; if(d<=dist[a][b])//假如距离小于到我的距离 { dist[a][b]=d;//则更新最小距离 if(!w) q.push_front({a,b});//假如为0，则放队头 else q.push_back({a,b});//假如为1，则放队尾 } } } return 0; } int main() { int T; cin>>T; while(T--) { cin>>n>>m; for(int i=0;i<n;i++) cin>>g[i]; if((n+m)&1) puts("NO SOLUTION");//分析可得，假如和在奇数点是无法到达的 else cout<<bfs()<<endl; } return 0; }
