2.4 最小步数模型
2.4.1 1107. 魔板
代码：
#include<bits/stdc++.h> using namespace std; char g[2][4]; string st,ed; map<string,int> dis; map<string,pair<char,string> > pre; void toM(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 getStr() { string str=""; for(int i=0;i<4;i++) { str+=g[0][i]; } for(int i=3;i>=0;i--) { str+=g[1][i]; } return str; } string opA(string str) { toM(str); for(int i=0;i<4;i++) { swap(g[0][i],g[1][i]); } return getStr(); } string opB(string str) { toM(str); char v0=g[0][3],v1=g[1][3]; for(int i=2;i>=0;i--) { g[0][i+1]=g[0][i]; g[1][i+1]=g[1][i]; } g[0][0]=v0,g[1][0]=v1; return getStr(); } string opC(string str) { toM(str); 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 getStr(); } void bfs(string st) { if(st==ed) return; queue<string> q; q.push(st); dis[st]=0; while(!q.empty()) { string top=q.front(); q.pop(); string tmp[3]; tmp[0]=opA(top); tmp[1]=opB(top); tmp[2]=opC(top); for(int i=0;i<3;i++) { if(dis.count(tmp[i])==0) { dis[tmp[i]]=dis[top]+1; pre[tmp[i]]=make_pair(i+'A',top); q.push(tmp[i]); if(tmp[i]==ed) return; } } } } int main() { for(int i=0;i<4;i++) { g[0][i]='1'+i; st+=g[0][i]; } for(int i=3,j=5;i>=0;i--,j++) { g[1][i]='0'+j; st+=g[1][i]; } for(int i=0;i<8;i++) { char c; cin>>c; ed+=c; } bfs(st); cout<<dis[ed]<<endl; string op=""; while(st!=ed) { op+=pre[ed].first; ed=pre[ed].second; } reverse(op.begin(),op.end()); if(op.length()!=0) cout<<op<<endl; return 0; }
2.5 双端队列广搜
2.5.1 175. 电路维修
代码：
#include<bits/stdc++.h> using namespace std; const int N=510; int T; int r,c; char g[N][N]; int dis[N][N]; bool st[N][N]; struct Node{ int x,y; }node; bool judge(int x,int y) { if(x>r||x<0||y>c||y<0) { return false; } return true; } int bfs() { int X[]={-1,-1,1,1},Y[]={-1,1,1,-1}; int ix[]={-1,-1,0,0},iy[]={-1,0,0,-1}; char cs[]="\\/\\/"; fill(dis[0],dis[0]+N*N,1e9); fill(st[0],st[0]+N*N,false); deque<Node> q; node.x=0,node.y=0; dis[0][0]=0; q.push_back(node); while(!q.empty()) { Node top=q.front(); q.pop_front(); if(st[top.x][top.y]) continue; st[top.x][top.y]=true; for(int i=0;i<4;i++) { int newX=top.x+X[i],newY=top.y+Y[i]; if(judge(newX,newY)) { int cx=top.x+ix[i],cy=top.y+iy[i]; int d=dis[top.x][top.y]+(g[cx][cy]!=cs[i]); if(d<dis[newX][newY]) { dis[newX][newY]=d; node.x=newX,node.y=newY; if(g[cx][cy]!=cs[i]) { q.push_back(node); } else q.push_front(node); } } } } return dis[r][c]; } int main() { cin>>T; while(T--) { cin>>r>>c; for(int i=0;i<r;i++) { cin>>g[i]; } int ans=bfs(); if(ans==1e9) cout<<"NO SOLUTION"<<endl; else cout<<ans<<endl; } return 0; }
2.6 双向广搜
2.6.1 190. 字串变换
代码：
#include<bits/stdc++.h> using namespace std; const int N=10; int n; string A,B; string a[N],b[N]; int extend(queue<string> &q,map<string,int> &ha,map<string,int> &hb,string a[],string b[]) { int tmp=ha[q.front()]; while(!q.empty()&&tmp==ha[q.front()]) { string t=q.front(); q.pop(); for(int i=0;i<n;i++) { for(int j=0;j<t.length();j++) { if(t.substr(j,a[i].length())==a[i]) { string r=t; r.replace(j,a[i].length(),b[i]); if(hb.count(r)) return ha[t]+hb[r]+1; if(ha.count(r)) continue; ha[r]=ha[t]+1; q.push(r); } } } } return 11; } int bfs() { queue<string> qa,qb; map<string,int> ha,hb; ha[A]=0,hb[B]=0; qa.push(A); qb.push(B); int step=0; while((!qa.empty())&&(!qb.empty())) { int t; if(qa.size()<qb.size()) t=extend(qa,ha,hb,a,b); else t=extend(qb,hb,ha,b,a); if(t<=10) return t; if(++step==10) return -1; } return -1; } int main() { cin>>A>>B; string x,y; while(cin>>x>>y) { a[n]=x,b[n]=y,n++; } int ans=bfs(); if(ans==-1) cout<<"NO ANSWER!"; else cout<<ans; return 0; }
2.7 A*
2.7.1 178. 第K短路
代码：
#include<bits/stdc++.h> using namespace std; const int N=1010,E=200010; typedef pair<int,int> PII; typedef pair<int,PII> PIII; int n,m; int S,T,K; int h[N],rh[N],e[E],w[E],ne[E],idx; int dist[N],f[N],cnt[N]; bool st[N]; void add(int h[],int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void djk() { fill(dist,dist+N,1e9); dist[T]=0; priority_queue<PII,vector<PII>,greater<PII> >heap; heap.push(make_pair(0,T)); while(heap.size()) { PII t=heap.top(); heap.pop(); int ver=t.second; if(st[ver]) continue; st[ver]=true; for(int i=rh[ver];i!=-1;i=ne[i]) { int j=e[i]; if(dist[j]>dist[ver]+w[i]) { dist[j]=dist[ver]+w[i]; heap.push(make_pair(dist[j],j)); } } } for(int i=0;i<n;i++) f[i]=dist[i]; } int a_star() { priority_queue<PIII,vector<PIII>,greater<PIII> > heap; heap.push(make_pair(dist[S],make_pair(0,S))); while(heap.size()) { PIII t=heap.top(); heap.pop(); int ver=t.second.second,distance=t.second.first; cnt[ver]++; if(cnt[T]==K) return distance; for(int i=h[ver];i!=-1;i=ne[i]) { int j=e[i]; if(cnt[j]<K) { heap.push(make_pair(distance+w[i]+f[j],make_pair(distance+w[i],j))); } } } return -1; } int main() { cin>>n>>m; fill(h,h+N,-1); fill(rh,rh+N,-1); for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; add(h,a,b,c),add(rh,b,a,c); } cin>>S>>T>>K; if(S==T) K+=1; djk(); cout<<a_star(); return 0; }
2.7.2 179. 八数码
代码：
#include<bits/stdc++.h> using namespace std; char g[3][3]; string a,b="12345678x"; unordered_map<string,pair<char,string> > pre; void toG(string s) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { g[i][j]=s[i*3+j]; } } } string toS() { string s=""; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { s+=g[i][j]; } } return s; } void getXY(int &x,int &y) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(g[i][j]=='x') { x=i,y=j; return; } } } } string opU(string s) { toG(s); int x,y; getXY(x,y); if(x!=0) { swap(g[x][y],g[x-1][y]); return toS(); } else return ""; } string opD(string s) { toG(s); int x,y; getXY(x,y); if(x!=2) { swap(g[x][y],g[x+1][y]); return toS(); } else return ""; } string opL(string s) { toG(s); int x,y; getXY(x,y); if(y!=0) { swap(g[x][y],g[x][y-1]); return toS(); } else return ""; } string opR(string s) { toG(s); int x,y; getXY(x,y); if(y!=2) { swap(g[x][y],g[x][y+1]); return toS(); } else return ""; } int bfs() { if(a==b) return 0; queue<string> q; q.push(a); pre[a]=make_pair('*',""); map<int,char> op; op[0]='u'; op[1]='d'; op[2]='l'; op[3]='r'; while(q.size()) { string t=q.front(); q.pop(); string tmp[4]; tmp[0]=opU(t); tmp[1]=opD(t); tmp[2]=opL(t); tmp[3]=opR(t); for(int i=0;i<4;i++) { if(tmp[i]!=""&&pre.count(tmp[i])==0) { q.push(tmp[i]); pre[tmp[i]]=make_pair(op[i],t); if(tmp[i]==b) return 1; } } } return -1; } int main() { for(int i=0;i<9;i++) { char c; cin>>c; a+=c; } int t=bfs(); if(t==-1) cout<<"unsolvable"; else { string ans=""; string tmp=b; while(tmp!=a) { ans+=pre[tmp].first; tmp=pre[tmp].second; } reverse(ans.begin(),ans.end()); cout<<ans; } return 0; } //2 3 4 1 5 x 7 6 8
2.8 DFS之连通性模型
2.8.1 1112. 迷宫
代码：
#include<bits/stdc++.h> using namespace std; const int N=110; int k,n; char g[N][N]; int sx,sy,ex,ey; bool st[N][N]; int X[]={1,-1,0,0},Y[]={0,0,1,-1}; bool judge(int x,int y) { if(x>=n||x<0||y>=n||y<0) return false; if(g[x][y]=='#'||st[x][y]==true) return false; return true; } bool dfs(int x,int y) { if(g[x][y]=='#') return false; if(x==ex&&y==ey) return true; st[x][y]=true; for(int i=0;i<4;i++) { int newX=x+X[i],newY=y+Y[i]; if(judge(newX,newY)) { if(dfs(newX,newY)) return true; } } return false; } int main() { cin>>k; while(k--) { cin>>n; for(int i=0;i<n;i++) { cin>>g[i]; } cin>>sx>>sy>>ex>>ey; fill(st[0],st[0]+N*N,false); if(sx==ex&&sy==ey&&g[ex][ey]!='#') cout<<"YES"<<endl; else if(g[sx][sy]=='#'||g[ex][ey]=='#') { cout<<"NO"<<endl; } else { bool flag=dfs(sx,sy); if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; } /* BFS #include<bits/stdc++.h> using namespace std; const int N=110; int k,n; char g[N][N]; int sx,sy,ex,ey; bool st[N][N]; int X[]={1,-1,0,0},Y[]={0,0,1,-1}; struct Node{ int x,y; }node; bool judge(int x,int y) { if(x>=n||x<0||y>=n||y<0) return false; if(g[x][y]=='#'||st[x][y]==true) return false; return true; } bool bfs() { if(g[sx][sy]=='#'||g[ex][ey]=='#') return false; fill(st[0],st[0]+N*N,false); queue<Node> q; node.x=sx,node.y=sy; q.push(node); st[sx][sy]=true; while(q.size()) { Node t=q.front(); q.pop(); for(int i=0;i<4;i++) { int newX=t.x+X[i],newY=t.y+Y[i]; if(judge(newX,newY)) { node.x=newX,node.y=newY; q.push(node); st[newX][newY]=true; if(ex==newX&&ey==newY) return true; } } } return false; } int main() { cin>>k; while(k--) { cin>>n; for(int i=0;i<n;i++) { cin>>g[i]; } cin>>sx>>sy>>ex>>ey; if(sx==ex&&sy==ey&&g[ex][ey]!='#') cout<<"YES"<<endl; else { bool flag=bfs(); if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; } */
2.8.2 1113. 红与黑
代码：
#include<bits/stdc++.h> using namespace std; const int N=30; char g[N][N]; int ans; int n,m; int sx,sy; int X[]={0,0,1,-1},Y[]={1,-1,0,0}; bool st[N][N]; bool judge(int x,int y) { if(x>=n||x<0||y>=m||y<0) return false; if(st[x][y]==true||g[x][y]=='#') return false; return true; } void dfs(int x,int y) { if(st[x][y]) return; st[x][y]=true; ans++; for(int i=0;i<4;i++) { int newX=x+X[i],newY=y+Y[i]; if(judge(newX,newY)) { dfs(newX,newY); } } return; } int main() { while(true) { cin>>m>>n; if(m==n&&n==0) break; for(int i=0;i<n;i++) { cin>>g[i]; } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(g[i][j]=='@') { sx=i,sy=j; } } } ans=0; fill(st[0],st[0]+N*N,false); dfs(sx,sy); cout<<ans<<endl; } return 0; }
2.9 DFS之搜索顺序
2.9.1 1116. 马走日
代码：
#include<bits/stdc++.h> using namespace std; const int N=10; int n,m,x,y; bool st[N][N]; int ans; int X[]={-1,1,-2,2,-2,2,-1,1},Y[]={-2,-2,-1,-1,1,1,2,2}; void dfs(int x,int y,int cnt) { if(cnt==n*m) { ans++; return; } st[x][y]=true; for(int i=0;i<8;i++) { int newX=x+X[i],newY=y+Y[i]; if(newX>=n||newX<0||newY>=m||newY<0) continue; if(st[newX][newY]) continue; dfs(newX,newY,cnt+1); } st[x][y]=false; } int main() { std::ios::sync_with_stdio(0); int T; cin>>T; while(T--) { cin>>n>>m>>x>>y; ans=0; dfs(x,y,1); cout<<ans<<endl; } return 0; }
