BFS的题目没什么好说的，通常优化都是判断可行性，或者状压以后记忆化。几道例题都非常基础。
#10027. 「一本通 1.4 例 2」魔板
暴力写出置换即可。
#include <bits/stdc++.h> using namespace std; int buf[9],tar,ans,src; char vis[99999999]; map <int,string > sta; void A() { swap(buf[1],buf[5]); swap(buf[2],buf[6]); swap(buf[3],buf[7]); swap(buf[4],buf[8]); } void B() { int t1=buf[4], t2=buf[8]; buf[4]=buf[3]; buf[8]=buf[7]; buf[3]=buf[2]; buf[7]=buf[6]; buf[2]=buf[1]; buf[6]=buf[5]; buf[1]=t1; buf[5]=t2; } void C() { int t=buf[2]; buf[2]=buf[6]; buf[6]=buf[7]; buf[7]=buf[3]; buf[3]=t; } int compress() { int ret = 0; for(int i=1;i<=8;i++) ret=ret*10+buf[i]; return ret; } void depress(int x) { for(int i=8;i>=1;--i) buf[i]=x%10, x/=10; } int main() { for(int i=1;i<=8;i++) cin>>buf[i]; swap(buf[5],buf[8]); swap(buf[6],buf[7]); tar = compress(); for(int i=1;i<=4;i++) buf[i]=i; for(int i=1;i<=4;i++) buf[8-i+1]=i+4; src = compress(); queue <int> q; q.push(src); string v; sta[src]=v; vis[src]=1; while(!q.empty()) { int p = q.front(); q.pop(); if(p==tar) { cout<<vis[p]-1<<endl; for(int i=0;i<sta[p].size();i++) cout<<sta[p][i]; return 0; } int tmp; depress(p); A(); tmp=compress(); if(vis[tmp]==0) { vis[tmp]=vis[p]+1; sta[tmp]=sta[p]; sta[tmp]+="A"; q.push(tmp); } depress(p); B(); tmp=compress(); if(vis[tmp]==0) { vis[tmp]=vis[p]+1; sta[tmp]=sta[p]; sta[tmp]+="B"; q.push(tmp); } depress(p); C(); tmp=compress(); if(vis[tmp]==0) { vis[tmp]=vis[p]+1; sta[tmp]=sta[p]; sta[tmp]+="C"; q.push(tmp); } } }
#10028. 「一本通 1.4 例 3」Knight Moves
#include <bits/stdc++.h> using namespace std; const int dx[9] = {0,2,1,-1,-2,-2,-1,1,2}, dy[9] = {0,1,2,2,1,-1,-2,-2,-1}; int n,l,sx,sy,tx,ty; int f[305][305]; int main(){ cin>>n; while(n--) { cin>>l>>sx>>sy>>tx>>ty; memset(f,0xff,sizeof f); queue <pair<int,int> >q; q.push(make_pair(sx,sy)); f[sx][sy]=0; while(!q.empty()) { int px=q.front().first, py=q.front().second; q.pop(); if(px==tx && py==ty) { break; } else { for(int i=1;i<=8;i++) { int nx=px+dx[i], ny=py+dy[i]; if(nx<0 || ny<0 || nx>=l || ny>=l) continue; if(f[nx][ny] < 0) { f[nx][ny]=f[px][py]+1; q.push(make_pair(nx,ny)); } } } } cout<<f[tx][ty]<<endl; } }
#10029. 「一本通 1.4 练习 1」棋盘游戏
#include <bits/stdc++.h> using namespace std; struct Status { char a[4][4]; int compress() { int tmp = 0; for(int i=0;i<4;i++) for(int j=0;j<4;j++) tmp+=(a[i][j]-'0')*(1<<(i*4+j)); return tmp; } void depress(int tmp) { for(int i=0;i<4;i++) for(int j=0;j<4;j++) a[i][j]=((tmp>>(i*4+j))&1) + '0'; } }; const int d[12][4] = {{1,1,1,2},{1,2,1,3},{1,3,1,4},{2,1,2,2},{2,2,2,3},{2,3,2,4}, {3,1,3,2},{3,2,3,3},{3,3,3,4},{4,1,4,2},{4,2,4,3},{4,3,4,4}}; int f[100005]; int main() { Status st,en; for(int i=0;i<4;i++) { string str; cin>>str; for(int j=0;j<4;j++) st.a[i][j]=str[j]; } for(int i=0;i<4;i++) { string str; cin>>str; for(int j=0;j<4;j++) en.a[i][j]=str[j]; } int tar = en.compress(); int src = st.compress(); memset(f,0xff,sizeof f); f[src] = 0; queue <int> q; q.push(src); int cnt = 0; while(!q.empty()) { int p = q.front(); q.pop(); if(p==tar) break; Status s; for(int i=0;i<12;i++) { s.depress(p); swap(s.a[d[i][0]-1][d[i][1]-1],s.a[d[i][2]-1][d[i][3]-1]); int tmp = s.compress(); if(f[tmp]<0) { f[tmp]=f[p]+1; q.push(tmp); } } for(int i=0;i<12;i++) { s.depress(p); swap(s.a[d[i][1]-1][d[i][0]-1],s.a[d[i][3]-1][d[i][2]-1]); int tmp = s.compress(); if(f[tmp]<0) { f[tmp]=f[p]+1; q.push(tmp); } } } cout<<f[tar]<<endl; }
#10030. 「一本通 1.4 练习 2」Keyboarding
一开始题目看错了WA了好几发
#include <bits/stdc++.h> using namespace std; struct Status { int x,y,z; int compress() { return z*2500+y*50+x; } void decompress(int tmp) { x=tmp%50; y=(tmp/50)%50; z=tmp/2500; } }; const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; int r,c; string s,tab[55]; int f[26000005]; pair<int,int> g[55][55][4]; int main() { cin>>r>>c; for(int i=0;i<r;i++) cin>>tab[i]; cin>>s; s+="*"; for(int j=0;j<r;j++) for(int k=0;k<c;k++) { for(int l=0;l<4;l++) { int x=j,y=k; int me=tab[j][k]; while(x>=0&&y>=0&&x<r&&y<c&&me==tab[x][y]) x+=dx[l],y+=dy[l]; if(x<0)x=j; if(y<0)y=k; if(x>=r)x=j;if(y>=c)y=k; g[j][k][l]=make_pair(x,y); } } memset(f,0xff,sizeof f); f[0]=0; queue <int> q; int len = s.length(); int cnt = 0; q.push(0); while(!q.empty()) {++cnt; int p=q.front(); q.pop(); Status st; st.decompress(p); char me = tab[st.x][st.y]; if(st.z==len) { cout<<f[p]<<endl; return 0; } for(int i=0;i<4;i++) { st.decompress(p); pair<int,int> to = g[st.x][st.y][i]; st.x=to.first; st.y=to.second; int tmp=st.compress(); if(f[tmp]<0) { f[tmp]=f[p]+1; q.push(tmp); } } st.decompress(p); if(tab[st.x][st.y]==s[st.z]) { st.z++; int tmp=st.compress(); f[tmp]=f[p]+1; q.push(tmp); } } //cout<<cnt<<endl; }
#10031. 「一本通 1.4 练习 3」移动玩具
#include <bits/stdc++.h> using namespace std; struct Status { char a[4][4]; int compress() { int tmp = 0; for(int i=0;i<4;i++) for(int j=0;j<4;j++) tmp+=(1<<(i*4+j))*(a[i][j]-'0'); return tmp; } void decompress(int tmp) { for(int i=0;i<4;i++) for(int j=0;j<4;j++) a[i][j] = ((tmp>>(i*4+j))&1) + '0'; } }; int f[100005]; const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; int main() { Status St,En; int st,en; for(int i=0;i<4;i++) { string tmp; cin>>tmp; for(int j=0;j<4;j++) St.a[i][j]=tmp[j]; } for(int i=0;i<4;i++) { string tmp; cin>>tmp; for(int j=0;j<4;j++) En.a[i][j]=tmp[j]; } st = St.compress(); en = En.compress(); memset(f,0xff,sizeof f); queue <int> q; q.push(st); f[st]=0; while(q.size()) { int p = q.front(); q.pop(); if(p==en) { cout<<f[p]<<endl; return 0; } Status s; s.decompress(p); for(int i=0;i<4;i++){ for(int j=0;j<4;j++) { if(s.a[i][j]=='0') continue; for(int l=0;l<4;l++) { int nx=i+dx[l],ny=j+dy[l]; if(nx<0||ny<0||nx>3||ny>3) continue; if(s.a[nx][ny]=='1') continue; swap(s.a[nx][ny],s.a[i][j]); int tmp = s.compress(); if(f[tmp]==-1) { f[tmp]=f[p]+1; q.push(tmp); } swap(s.a[nx][ny],s.a[i][j]); } } } } }