Multi-source BFS
1. Matrix distance
Titlehttps://www.acwing.com/problem/content/description/175/
#include <bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> PII; const int N=1010; char g[N][N]; int dist[N][N]; PII q[N*N]; int n,m; int dx[]={-1,0,1,0},dy[]={0,-1,0,1}; void bfs() { memset(dist,-1, sizeof dist); int hh=0,tt=-1; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j]=='1') { dist[i][j]=0; q[ + + tt]={i,j}; } while(hh<=tt) { auto t=q[hh++]; for(int i=0;i<4;i++) { int xx=t.x + dx[i],yy=t.y + dy[i]; if(xx<0||xx>=n||yy<0||yy>=m)continue; if(dist[xx][yy]!=-1)continue; dist[xx][yy]=dist[t.x][t.y] + 1; q[ + + tt]={xx,yy}; } } } int main() { cin>>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++) cout<<dist[i][j]<<" "; cout<<endl; } }
Minimum step model
Magic Board
Titlehttps://www.acwing.com/problem/content/description/1109/
#include <bits/stdc++.h> using namespace std; char g[2][8]; unordered_map<string,int> dist; unordered_map<string,pair<char,string>> pre; queue<string> q; void Set(string str) { for(int i=0;i<4;i ++ )g[0][i]=str[i]; for(int i=3,j=4;i>=0;i--,j + + )g[1][i]=str[j]; } string get() { string res; for(int i=0;i<4;i + + )res + =g[0][i]; for(int i=3;i>=0;i--)res + =g[1][i]; return res; } string move0(string state) { Set(state); for(int i=0;i<4;i++) swap(g[0][i],g[1][i]); return get(); } string move1(string state) { Set(state); char v0=g[0][3],v1=g[1][3]; for(int i=3;i>0;i--) for(int j=0;j<2;j++) g[j][i]=g[j][i-1]; g[0][0]=v0,g[1][0]=v1; return get(); } string move2(string state) { Set(state); char v=g[0][1]; g[0][1]=g[1][1]; g[1][1]=g[1][2]; g[1][2]=g[0][2]; g[0][2]=v; return get(); } void bfs(string start, string end) { if(start==end) return; q. push(start); dist[start]=0; while(q. size()) { auto t=q. front(); q. pop(); string m[3]; m[0]=move0(t); m[1]=move1(t); m[2]=move2(t); for(int i=0;i<3;i++) { string str=m[i]; if(dist.count(str)==0) { dist[str]=dist[t] + 1; pre[str]={char(i + 'A'),t}; if(str==end)break; q. push(str); } } } } int main() { string start, end; for(int i=0;i<8;i ++ ) { int x; cin>>x; end + =char(x + '0'); } for(int i=0;i<8;i + + )start + =char(i + '1'); bfs(start,end); cout<<dist[end]<<endl; string res; while(end!=start) { res + =pre[end].first; end=pre[end].second; } reverse(res.begin(),res.end()); if(res. size()) cout<<res; }
Double-ended queue wide search (when the weight is only 0 and 1)
circuit repair
Titlehttps://www.acwing.com/problem/content/description/177/
Solutionhttps://www.acwing.com/solution/content/21775/
#include <bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> PII; const int N=550; char g[N][N]; int dist[N][N]; bool st[N][N]; int n,m; char cs[5]="\/\/";//Four standard directions\/\/, used to compare whether the directions on the map are consistent int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1};//direction of conversion, \/\/ int ix[]={-1,-1,0,0},iy[]={-1,0,0,-1};//corresponding to the coordinates of the map\/\/ int bfs() { deque<PII> q;//double-ended queue memset(st,0,sizeof st);//clear state memset(dist,0x3f,sizeof dist);//clear the distance q.push_back({0,0}); dist[0][0]=0; while(q. size()) { auto t=q. front(); q. pop_front(); int x=t.x,y=t.y; if(x==n & amp; & amp;y==m) return dist[x][y];//If n and m have been found, return directly 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]);//Check if the original image is in the same direction as my transfer, if it is 0, anyway it is 1 int d = dist[x][y] + w; if(d<dist[a][b])//If the distance is less than the distance to me { dist[a][b]=d;//Then update the minimum distance if(!w)q.push_front({a,b});//If it is 0, put the front of the queue else q.push_back({a,b});//If it is 1, put it at the end of the queue } } } return -1;//will not be executed } int main() { int t; cin>>t; while(t--) { cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>g[i][j]; if( n + m & amp; 1) cout<<"NO SOLUTION"<<endl;//Analysis is available, if the sum is unreachable at odd points else cout<<bfs()<<endl; } }