0x25广度优先搜索+0x26广搜变形

1.一般bfs

AcWing 172. 立体推箱子 

#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[505][505];
int vis[3][505][505];
int df[3][4]={{1,1, 2,2},{0,0,1,1}, {0,0,2,2}};
int dx[3][4]={{0,0,1,-2},{0,0,1,-1},{2,-1,0,0}};
int dy[3][4]={{1,-2,0,0},{2,-1,0,0},{0,0,1,-1}};
struct S{int f,x,y,st;void print(){printf("(%d,%d,%d)\n",this->f,this->x,this->y);}
}st,ed;
bool operator==(S a,S b){return a.f==b.f&&a.x==b.x&&a.y==b.y;
} 
bool check(int f,int x,int y){if(s[x][y]=='#')return 0; if(f==0){if(s[x][y]=='E')return 0;}if(f==1){if(s[x][y+1]=='#')return 0;}if(f==2){if(s[x+1][y]=='#')return 0;} return 1;
}
//0 x//1 xx
//  ^
//2 x<
//  x
void prework(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='X'){if(s[i][j+1]=='X'){s[i][j+1]='.';st={1,i,j,0};}else if(s[i+1][j]=='X'){s[i+1][j]='.';st={2,i,j,0};}else{st={0,i,j,0};}s[i][j]='.';}if(s[i][j]=='O'){if(s[i][j+1]=='O'){s[i][j+1]='.';ed={1,i,j,0};}else if(s[i+1][j]=='O'){s[i+1][j]='.';ed={2,i,j,0};}else{ed={0,i,j,0};}s[i][j]='.';}}}
}
queue<S>q;
int main(){while(~scanf("%d%d",&n,&m)&&n&&m){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)vis[0][i][j]=vis[1][i][j]=vis[2][i][j]=0;while(!q.empty())q.pop();for(int i=1;i<=n;i++){scanf("%s",s[i]+1);}for(int i=1;i<=n;i++){s[i][0]=s[i][m+1]='#';}for(int j=1;j<=m;j++){s[0][j]=s[n+1][j]='#';}prework();q.push(st);vis[st.f][st.x][st.y]=1;int fd=0;while(q.size()){int f=q.front().f,x=q.front().x,y=q.front().y,st=q.front().st;q.pop();//printf("%d:(%d,%d,%d)\n",st,f,x,y);if(f==ed.f&&x==ed.x&&y==ed.y){fd=1;printf("%d\n",st);break;}for(int i=0;i<4;i++){int nx=x+dx[f][i],ny=y+dy[f][i],nf=df[f][i];if(vis[nf][nx][ny])continue;vis[nf][nx][ny]=1;if(check(nf,nx,ny)){q.push({nf,nx,ny,st+1});}}}if(!fd)printf("Impossible\n");}return 0;
}

 AcWing 192. 立体推箱子2 

先到一个点（a,b,0)满足a%3==0&&b%3==0

然后横着走再竖着走a/3*2+b/3*2步，这样是最快的

考虑（a，b）不会距离原点太远，限制距离广搜即可，同上一题

#include<bits/stdc++.h>
using namespace std;
long long dx[3][4]={{0,0,1,-2},{0,0,1,-1},{0,0,2,-1}};
long long dy[3][4]={{1,-2,0,0},{2,-1,0,0},{1,-1,0,0}};
long long dz[3][4]={{1,1,2,2} ,{0,0,1,1} ,{2,2,0,0}};
char op[3];
long long X,Y,z,ans=1e9;
map<pair<long long,pair<long long,long long> > ,long long>mp;
void bfs(long long x,long long y,long long z){mp.clear();queue<pair<long long,pair<long long,long long> > >q;q.push({x,{y,z}});mp[{x,{y,z}}]=1;while(q.size()){while(!q.empty()){long long x=q.front().first,y=q.front().second.first,z=q.front().second.second;q.pop();if(x%3==0&&y%3==0&&z==0){ans=min(ans,mp[{x,{y,z}}]-1+abs(x)/3*2+abs(y)/3*2);}long long xx,yy,zz;for(long long i=0;i<4;i++){xx=x+dx[z][i],yy=y+dy[z][i],zz=dz[z][i];if(xx-X<-15||xx-X>15||yy-Y<-15||yy-Y>15)continue;if(!mp[{xx,{yy,zz}}]){mp[{xx,{yy,zz}}]=mp[{x,{y,z}}]+1;q.push({xx,{yy,zz}});}}}}
}
int main(){while(~scanf("%s%lld%lld",op,&X,&Y)){ans=2e9;if(op[0]=='U'){z=0;}else if(op[0]=='H'){z=1;}else{z=2;}bfs(X,Y,z);printf("%lld\n",ans);}return 0;
}

AcWing 173. 矩阵距离 

多起点是广搜

#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[1005][1005];
int d[1005][1005];
queue<pair<int,int> >q;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",s[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){d[i][j]=-1;if(s[i][j]=='1'){d[i][j]=0;q.push({i,j});}}while(!q.empty()){int x=q.front().first,y=q.front().second;q.pop();for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(d[xx][yy]!=-1)continue;d[xx][yy]=d[x][y]+1;q.push({xx,yy});}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%d ",d[i][j]);}printf("\n");}return 0;
}

AcWing 174. 推箱子 

状态是一个箱子与人的方向，记录上一步从何处转来

#include<bits/stdc++.h>
using namespace std;
int n,m,T,stmx,stmy,stbx,stby,edx,edy,dm[25][25],la[25][25];
string str;
pair<int,int>db[25][25][4];char s[25][25];
int dxx[]={1,-1,0,0};
int dyy[]={0,0,1,-1};
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
struct S{int x,y,f;
}lab[25][25][4];;
queue<S>q;
bool hf(int x,int y){return (x>=1&&x<=n&&y>=1&y<=m)&&s[x][y]!='#';
}
int bfs(pair<int,int>st,pair<int,int>ed,int x,int y){queue<pair<int,int> >q;q.push(st);memset(dm,0x3f,sizeof(dm));memset(la,0,sizeof(la));dm[st.first][st.second]=0;while(!q.empty()){pair<int,int> k=q.front();if(k==ed){return dm[k.first][k.second];}q.pop();for(int i=0;i<4;i++){int xx=k.first+dx[i],yy=k.second+dy[i];if(hf(xx,yy)&&(xx!=x||yy!=y)&&dm[xx][yy]>dm[k.first][k.second]+1){dm[xx][yy]=dm[k.first][k.second]+1;la[xx][yy]=i;q.push({xx,yy});}}}return -1;
}
void prework(){while(q.size())q.pop();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='S'){stmx=i,stmy=j;s[i][j]='.';}if(s[i][j]=='B'){stbx=i,stby=j;s[i][j]='.';}if(s[i][j]=='T'){edx=i,edy=j;s[i][j]='.';}}}for(int i=0;i<4;i++){int xx=stbx+dxx[i],yy=stby+dyy[i];if(hf(xx,yy)){int res=bfs({stmx,stmy},{xx,yy},stbx,stby);if(res!=-1){db[stbx][stby][i]={0,res};q.push({stbx,stby,i});}}}
}
void pprint(int x,int y,int xx,int yy){if(x==xx&&y==yy)return;while(x!=xx||y!=yy){if(la[x][y]==0){str+='n';}else if(la[x][y]==1){str+='s';}  else if(la[x][y]==2){str+='w';}else{str+='e';}int p=la[x][y];x=x+dxx[p],y=y+dyy[p];}
}
void print(S a){a=lab[a.x][a.y][a.f];while(a.x){if(a.f==0){str+='N';}else if(a.f==1){str+='S';}  else if(a.f==2){str+='W';}else{str+='E';}S b=lab[a.x][a.y][a.f];if(b.x){bfs({b.x,b.y},{a.x+dxx[a.f],a.y+dyy[a.f]},a.x,a.y);pprint(a.x+dxx[a.f],a.y+dyy[a.f],b.x,b.y); }else{bfs({stmx,stmy},{a.x+dxx[a.f],a.y+dyy[a.f]},a.x,a.y);pprint(a.x+dxx[a.f],a.y+dyy[a.f],stmx,stmy);}a={b.x,b.y,b.f};}
}
int main(){while(~scanf("%d%d",&n,&m)&&n&&m){memset(lab,0,sizeof(lab));str="";printf("Maze #%d\n",++T);for(int i=1;i<=n;i++)scanf("%s",s[i]+1);for(int i=1;i<=n;i++)s[i][0]=s[i][m+1]='#';for(int j=1;j<=m;j++)s[0][j]=s[n+1][j]='#';memset(db,0x3f,sizeof(db));prework();while(!q.empty()){int x=q.front().x,y=q.front().y,f=q.front().f;q.pop();int xx=x+dx[f],yy=y+dy[f];if(hf(xx,yy)){for(int i=0;i<4;i++){int xxx=xx+dxx[i],yyy=yy+dyy[i];int res=bfs({x,y},{xxx,yyy},xx,yy);if(res!=-1&&make_pair(db[x][y][f].first+1,db[x][y][f].second+res)<db[xx][yy][i]){db[xx][yy][i]=make_pair(db[x][y][f].first+1,db[x][y][f].second+res);lab[xx][yy][i]={x,y,f};q.push({xx,yy,i});}}}}pair<int,int>ans={2e9,2e9};S ed;for(int i=3;i>=2;i--){if(ans>db[edx][edy][i]){ed={edx,edy,i};ans=db[edx][edy][i];}}for(int i=1;i>=0;i--){if(ans>db[edx][edy][i]){ed={edx,edy,i};ans=db[edx][edy][i];}}if(ans==make_pair(0x3f3f3f3f,0x3f3f3f3f)){printf("Impossible.\n\n");}else{print(ed);reverse(str.begin(),str.end());cout<<str;printf("\n\n");}} return 0;
}

 AcWing 191. 天气预报 

其实深搜更适合

关键问题是任何地区都不能连续七天或以上时间都不降雨。

经过观察，只要四个角满足，那么都满足了

所以状态（天数，四个角，云的位置）

#include<bits/stdc++.h>
using namespace std;
int n,fd=0; 
int dx[]={0,0,0,0,0,1,2,-1,-2};
int dy[]={0,1,2,-1,-2,0,0,0,0};
int a[366][4][4];
int vis[366][3][3][7][7][7][7];
bool check(int d,int x,int y,int p1,int p2,int p3,int p4){if(x>=0&&x<=2&&y>=0&&y<=2&&p1<7&&p2<7&&p3<7&&p4<7&&a[d][x][y]==0&&a[d][x+1][y]==0&&a[d][x][y+1]==0&&a[d][x+1][y+1]==0){return 1;}return 0;
}
void dfs(int d,int x,int y,int p1,int p2,int p3,int p4){if(d==n){fd=1;return ;}if(vis[d][x][y][p1][p2][p3][p4])return;int xx,yy,pp1,pp2,pp3,pp4;vis[d][x][y][p1][p2][p3][p4]=1;for(int f=0;f<9;f++){xx=x+dx[f],yy=y+dy[f],pp1=p1+1,pp2=p2+1,pp3=p3+1,pp4=p4+1;if(xx==0&&yy==0){pp1=0;}if(xx==0&&yy==2){pp2=0;}if(xx==2&&yy==0){pp3=0;}if(xx==2&&yy==2){pp4=0;}if(check(d+1,xx,yy,pp1,pp2,pp3,pp4)){dfs(d+1,xx,yy,pp1,pp2,pp3,pp4);}}return ;
}
int main(){while(~scanf("%d",&n)&&n){memset(vis,0,sizeof(vis));for(int d=1;d<=n;d++){for(int i=0;i<=3;i++){for(int j=0;j<=3;j++){scanf("%d",&a[d][i][j]);}}}if(!check(1,1,1,1,1,1,1)){printf("0\n");continue;}fd=0;dfs(1,1,1,1,1,1,1);printf("%d\n",fd);}return 0;
}

2.双端队列bfs

AcWing 175. 电路维修 

由格点建点，又是否转动加01边

#include<bits/stdc++.h>
using namespace std;
int T,n,m,vis[505][505],d[505][505];char s[505][505];
int dx[]={-1,1,-1,1};
int dy[]={-1,1,1,-1};
int calc(int x,int y,int i){if(i==0){if(s[x][y]!='/')return 0;else return 1;}if(i==1){if(s[x+1][y+1]!='/')return 0;else return 1;}if(i==2){if(s[x][y+1]=='/')return 0;else return 1;}if(s[x+1][y]=='/')return 0;else return 1;
}
int main(){cin>>T;while(T--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",s[i]+1);}memset(vis,0,sizeof(vis));memset(d,0x3f,sizeof(d));deque<pair<int,int> >q;q.push_front({0,0});d[0][0]=0;while(!q.empty()){int x=q.front().first,y=q.front().second;q.pop_front();//printf("%d %d %d\n",x,y,d[x][y]);if(vis[x][y])continue;vis[x][y]=1;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx<0||xx>n||yy<0||yy>m)continue ;int v=calc(x,y,i);d[xx][yy]=min(d[x][y]+v,d[xx][yy]);if(v==0)q.push_front({xx,yy});else q.push_back({xx,yy});} }if(d[n][m]==0x3f3f3f3f)printf("NO SOLUTION\n");else printf("%d\n",d[n][m]);}return 0;
}

 AcWing 188. 武士风度的牛

简单题

#include<bits/stdc++.h>
using namespace std;
int n,m,vis[155][155];
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
char s[155][155];
struct S{int x,y,st;
}st,e;
queue<S>q;
void prework(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='K'){st={i,j,0};}if(s[i][j]=='H'){e={i,j,0}; } }}
}
int main(){scanf("%d%d",&m,&n);for(int i=1;i<=n;i++){scanf("%s",s[i]+1);}prework();q.push(st);vis[st.x][st.y]=1;while(q.size()){int  x=q.front().x,y=q.front().y,z=q.front().st;q.pop();if(x==e.x&&y==e.y){printf("%d",z);return 0;}for(int i=0;i<8;i++){int xx=x+dx[i];int yy=y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&s[xx][yy]!='*'&&(!vis[xx][yy])){vis[xx][yy]=1;q.push({xx,yy,z+1});}            }}return 0;
}

 AcWing 189. 乳草的入侵 

简单题

#include<bits/stdc++.h>
using namespace std;
int n,m,mx,my,vis[105][105],ans;
char s[105][105];
int dx[]={0,0,-1,1,-1,-1,1,1};
int dy[]={-1,1,0,0,-1,1,-1,1};
struct S{int x,y,st;
};
queue<S>q;
bool check(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='*'&&!vis[x][y];
}
int main(){scanf("%d%d%d%d",&m,&n,&my,&mx);mx=n-mx+1;for(int i=1;i<=n;i++)scanf("%s",s[i]+1);q.push({mx,my,0});vis[mx][my]=1;while(!q.empty()){int x=q.front().x,y=q.front().y,st=q.front().st;q.pop();ans=max(ans,st);for(int i=0;i<8;i++){int xx=x+dx[i],yy=y+dy[i];if(check(xx,yy)){vis[xx][yy]=1;q.push({xx,yy,st+1});}}}printf("%d",ans);return 0;
}

3.优先队列bfs

优先队列一定存权值

1加油2跑

#include<bits/stdc++.h>
using namespace std;
int n,m,p[1005],dist[1005][105],vis[1005][105];
int head[1005],nxt[20005],v[20005],e[20005],tot;
int c,s,ed,Q;
void add(int a,int b,int c){nxt[++tot]=head[a];v[tot]=b,e[tot]=c;head[a]=tot;
}
struct S{int num,id,c;friend bool operator<(S a,S b){return a.num>b.num;}
};
priority_queue<S>q,eq;
void bfs(){q=eq;memset(vis,0,sizeof(vis));memset(dist,0x3f,sizeof(dist));dist[s][0]=0;q.push({0,s,0});while(!q.empty()){int x=q.top().id,y=q.top().c;if(x==ed)return ;q.pop();if(vis[x][y])continue;vis[x][y]=1;if(y<c){if(dist[x][y+1]>dist[x][y]+p[x]){dist[x][y+1]=dist[x][y]+p[x];q.push({dist[x][y+1],x,y+1});}  }for(int i=head[x];i;i=nxt[i]){if(y>=e[i]){if(dist[v[i]][y-e[i]]>dist[x][y]){dist[v[i]][y-e[i]]=dist[x][y];q.push({dist[x][y],v[i],y-e[i]});}} }}
}
int main(){scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%d",&p[i]);}for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}cin>>Q;while(Q--){scanf("%d%d%d",&c,&s,&ed);bfs();if(!q.size())printf("impossible\n");else printf("%d\n",q.top().num);}return 0;
}

4.双向bfs

AcWing 177. 噩梦 

注意鬼先走

#include<bits/stdc++.h>
using namespace std;
int T,n,m,tot,t;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
struct S{int x,y,s;
}z[3],b,g;
char s[805][805];
int vis1[805][805],vis2[805][805],k[805][805],SS;
queue<S>q1,q2;
void print(){printf("%d\n",t);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%d",vis1[i][j]);}printf(" ");for(int j=1;j<=m;j++){printf("%d",vis2[i][j]);}printf("\n");}
}
void prework(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='Z'){z[++tot]={i,j,0};}if(s[i][j]=='M'){b={i,j,0};}if(s[i][j]=='G'){g={i,j,0};}}}
}
bool check(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='X'&&abs(x-z[1].x)+abs(y-z[1].y)>2*t&&abs(x-z[2].x)+abs(y-z[2].y)>2*t;
}
int bfs1(){while(q1.size()&&q1.front().s<t*3){int x=q1.front().x,y=q1.front().y,s=q1.front().s;q1.pop();if(!check(x,y))continue;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];SS=s;if(check(xx,yy)&&vis1[xx][yy]==0){vis1[xx][yy]=1;if(vis2[xx][yy])return 1;q1.push({xx,yy,s+1});}}}return 0;
}
int bfs2(){while(q2.size()&&q2.front().s<t){int x=q2.front().x,y=q2.front().y,s=q2.front().s;q2.pop();if(!check(x,y))continue;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(check(xx,yy)&&vis2[xx][yy]==0){vis2[xx][yy]=1;if(vis1[xx][yy])return 1;q2.push({xx,yy,s+1});}}}return 0;
}
int BFS(){while(q1.size())q1.pop();while(q2.size())q2.pop();q1.push(b);q2.push(g);vis1[b.x][b.y]=1;vis2[g.x][g.y]=1;t=0;while(q1.size()||q2.size()){t++;if(q1.size())if(bfs1())return t;if(q2.size())if(bfs2())return t;}return -1;
}
int main(){int p;cin>>p;while(p--){tot=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",s[i]+1);}prework();//printf("%d %d\n",b.x,b.y);//printf("%d %d\n",g.x,g.y);//printf("%d %d\n",z[1].x,z[1].y);//printf("%d %d\n",z[2].x,z[2].y);memset(vis1,0,sizeof(vis1));memset(vis2,0,sizeof(vis2));printf("%d\n",BFS());}return 0;
}

 AcWing 190. 字串变换 

普通搜索，O（（LN)^10）

取L20，N取6，120^10;

不可接受

由于初始状态和最终状态都是确定的，都可扩展

始态走一步，终态走一步，O（2*（LN)^5)

又不可能真的取到最大，所以开O2可以过，呵呵没想到acwing可以开O2，调了1个小时

#include<bits/stdc++.h>
typedef unsigned int ull;
using namespace std;
string a,b,x,y,now,t,s;
unordered_map<ull,vector<string> >mp1,mp2;
unordered_map<ull,bool>vis1,vis2;
queue<pair<string,int> >q1,q2;
vector<string>d;
int t1,t2,st;
inline ull h(string s){ull res=0;for(register int i=0;i<s.size();i++)res=res*1331+s[i];return res;
}
int bfs(queue<pair<string,int> >&q,int lim,unordered_map<ull,vector<string> >&mp,unordered_map<ull,bool >&vis,unordered_map<ull,bool >&check){while(!q.empty()&&q.front().second<lim){s=q.front().first;st=q.front().second;q.pop();register int i,j,k;ull o;for(i=s.size()-1;i>=0;i--){t="",o=0;for(j=i;j<s.size();j++){t+=s[j],o=o*1331+s[j];if(mp.find(o)!=mp.end()){d=mp[o];for( k=0;k<d.size();k++){now=s.substr(0,i)+d[k]+s.substr(j+1,s.size()-j);ull x=h(now);if(vis[x]!=1){if(check.find(x)!=check.end()){return 1;}vis[x]=1;q.push({now,st+1});}}}}}}return 0;
}
inline int bid_bfs(){while(q1.size()||q2.size()){if(q2.size())t2++;if(t1+t2>10)return -1;if(q2.size())if(bfs(q2,t2,mp2,vis2,vis1))return t1+t2;if(q1.size())t1++;if(t1+t2>10)return -1;if(q1.size())if(bfs(q1,t1,mp1,vis1,vis2))return t1+t2;}return -1;
}
int main(){//freopen("a.in","r",stdin);cin>>a>>b;if(a==b){printf("0");return 0;}q1.push({a,0});q2.push({b,0});vis1[h(a)]=1;vis2[h(b)]=1;while(cin>>x>>y){mp1[h(x)].push_back(y);mp2[h(y)].push_back(x);}int ans=bid_bfs();if(ans==-1)cout<<"NO ANSWER!";else cout<<ans;return 0;
}
/*
ab abbbbbbbbbbb
b bb
*/