【Ybt OJ】[基础算法 第5章] 广度搜索 [后半章]

$「$基础算法$」$ 第$5$章 广度搜索$($后$3$题$)$

前半章$link$

目录：

D.荆轲刺秦王
E.电路维修
F.逃离噩梦

又臭又长的$code$

$D.$ 例题$4$ 荆轲刺秦王

洛谷$link$

分析：

由于一本通上的数据较水 可以直接$bfs$模拟
先找出起点终点的位置 然后把图转化成$01$图
也就是可以直接看哪个位置 可以走 节省空间 方便处理
关于技能：
隐身：判断不合法时不用考虑$01$图就行
瞬移：在方向数组里多加$4$个方向 多走几步即可

然后我们直接处理技能的 使用情况即可.
洛谷上的要先加个差分优化

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue> 
//#pragma GCC optimize(2)
#define reg register 
using namespace std;
typedef long long ll;
typedef double db;
const int N=355;
struct node{int x,y,step,ab1,ab2;};
struct answer{int stp,abu1,abu2;};
int n,m,c1,c2,d,sx,sy,ex,ey;
queue<node> q;
bool G[N][N],vis[N][N];
bool check(int x,int y){if(x<1||x>n||y<1||y>m||vis[x][y]||G[x][y]) return false;  //不合法return true;
}
bool Invisible(int x,int y){if(x<1||x>n||y<1||y>m||vis[x][y]) return false;  //隐身return true;
}
answer bfs()
{int dx[12][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1},{d,0},{-d,0},{0,d},{0,-d}};//多加瞬移while(!q.empty()){node qwq=q.front();q.pop();if(qwq.x==ex&&qwq.y==ey)  //成功刺杀{answer kkk_;kkk_.abu1=c1-qwq.ab1;kkk_.abu2=c2-qwq.ab2;kkk_.stp=qwq.step;return kkk_;}for(int i=0;i<8;i++)  //正常走{node awa=qwq;awa.x+=dx[i][0];awa.y+=dx[i][1];awa.step++;if(check(awa.x,awa.y)){q.push(awa);vis[awa.x][awa.y]=1;}}if(qwq.ab1!=0)  //有隐身可以用{for(int i=0;i<8;i++){node qaq=qwq;qaq.x+=dx[i][0];qaq.y+=dx[i][1];qaq.step++;qaq.ab1--;  //使用次数--if(Invisible(qaq.x,qaq.y)){q.push(qaq);vis[qaq.x][qaq.y]=1;}}}if(qwq.ab2!=0)  //可以用瞬移{for(int i=8;i<12;i++)   //瞬移着走{node ovo=qwq;ovo.x+=dx[i][0];ovo.y+=dx[i][1];ovo.step++;ovo.ab2--;  //使用--if(check(ovo.x,ovo.y)){q.push(ovo);vis[ovo.x][ovo.y];}} }if(qwq.ab1!=0&&qwq.ab2!=0)  //同时用{for(int i=8;i<12;i++){node tut=qwq;tut.x+=dx[i][0];tut.y+=dx[i][1];tut.step++;tut.ab1--;tut.ab2--;  //两个技能都--if(Invisible(tut.x,tut.y)){q.push(tut);vis[tut.x][tut.y]=1;}}}}answer ans;ans.abu1=0x3f3f3f3f;ans.abu2=0x3f3f3f3f;ans.stp=-1;return ans;
}
int main(){scanf("%d%d%d%d%d",&n,&m,&c1,&c2,&d);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char c;cin>>c;if(c=='S'){sx=i;sy=j;} else if(c=='T'){ex=i;ey=j;}  //起点终点else if(c=='.') G[i][j]=0;  //01图else{vis[i][j]=1;G[i][j]=1;for(int k=1;k<=n;k++)for(int l=1;l<=m;l++)if(abs(k-i)+abs(l-j)<c-'0') G[k][l]=1;  //卫兵}}}node st;st.x=sx;st.y=sy;st.step=0;st.ab1=c1;st.ab2=c2;q.push(st);answer ans=bfs();if(ans.abu1==0x3f3f3f3f&&ans.abu2==0x3f3f3f3f) puts("-1");else printf("%d %d %d",ans.stp,ans.abu1,ans.abu2);return 0; 
}

$E.$ 例题$5$ 电路维修

洛谷$link$

分析：

地图大小是$(n+1)\ast (m+1)$的
所以点要从$0$开始 电线是从$1$开始的
在搜索时 搜到点的时候坐标要$-1$ 电线就正常处理
然后用一个数组存电路方向 跑$bfs$
再处理电线四个方向的联通：
$左上$ $左下$ $右上$ $右下$ 看能不能走完即可
也可以用最短路写
这个$bfs$在洛谷会$TLE$ 要双端队列$bfs$

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue> 
#pragma GCC optimize(2)
#define reg register 
using namespace std;
typedef long long ll;
typedef double db;
const int N=505;
struct node{int dis,x,y;
}qwq;
bool direc[N][N];
int n,m,T,ans,upd[N][N];
queue<node> q;
char c;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
bool check(int x,int y)
{if(x<0||x>n||y<0||y>m) return false;return true;
}
bool bfs()
{//while(!q.empty()) q.pop();q.push((node){0,0,0});upd[0][0]=0;while(!q.empty()){qwq=q.front();q.pop();if(qwq.dis>=ans) continue;if(qwq.x==n&&qwq.y==m){ans=qwq.dis;continue;} //右上 if(check(qwq.x-1,qwq.y+1)&&(upd[qwq.x-1][qwq.y+1]==-1||upd[qwq.x-1][qwq.y+1]>(qwq.dis+(direc[qwq.x][qwq.y+1]!=0)))){upd[qwq.x-1][qwq.y+1]=qwq.dis+(direc[qwq.x][qwq.y+1]!=0);q.push((node){qwq.dis+(direc[qwq.x][qwq.y+1]!=0),qwq.x-1,qwq.y+1});}//左上if(check(qwq.x-1,qwq.y-1)&&(upd[qwq.x-1][qwq.y-1]==-1||upd[qwq.x-1][qwq.y-1]>(qwq.dis+(direc[qwq.x][qwq.y]!=1)))){upd[qwq.x-1][qwq.y-1]=qwq.dis+(direc[qwq.x][qwq.y]!=1);q.push((node){qwq.dis+(direc[qwq.x][qwq.y]!=1),qwq.x-1,qwq.y-1});} //右下 if(check(qwq.x+1,qwq.y+1)&&(upd[qwq.x+1][qwq.y+1]==-1||upd[qwq.x+1][qwq.y+1]>(qwq.dis+(direc[qwq.x+1][qwq.y+1]!=1)))){upd[qwq.x+1][qwq.y+1]=qwq.dis+(direc[qwq.x+1][qwq.y+1]!=1);q.push((node){qwq.dis+(direc[qwq.x+1][qwq.y+1]!=1),qwq.x+1,qwq.y+1});}//左下if(check(qwq.x+1,qwq.y-1)&&(upd[qwq.x+1][qwq.y-1]==-1||upd[qwq.x+1][qwq.y-1]>(qwq.dis+(direc[qwq.x+1][qwq.y]!=0)))){upd[qwq.x+1][qwq.y-1]=qwq.dis+(direc[qwq.x+1][qwq.y]!=0);q.push((node){qwq.dis+(direc[qwq.x+1][qwq.y]!=0),qwq.x+1,qwq.y-1});}}if(ans==2147483647) return 0;return 1; 
}
int main(){T=read();while(T--){memset(upd,-1,sizeof(upd));ans=2147483647;n=read();m=read();for(reg int i=1;i<=n;i++)for(reg int j=1;j<=m;j++){cin>>c;if(c=='/') direc[i][j]=0;else direc[i][j]=1;}if(bfs()==0) puts("NO SOLUTION");else printf("%d\n",ans);}	return 0; 
}

$F.$ 例题$6$ 逃离噩梦

分析：

要分别处理男孩和女孩的行踪 男孩$1$次$3$步 女孩就正常走
墙不能走的 包括鬼们本身的位置 也不能走
每次走前除了判断合法 还要看走完这一步会不会被鬼抓 也就是在鬼坐标的曼哈顿距离内
男孩走$3$步 可以先做$3$次搜索 再计$1$步就可以
先把男孩女孩坐标找出 当起点终点
然后按上面思路$bfs$ 看男孩行踪与女孩行踪重合即可.

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue> 
//#pragma GCC optimize(2)
#define reg register 
using namespace std;
typedef long long ll;
typedef double db;
const int N=1005;
struct node{int x,y,dis;
}qwq;
int T,n,m,Bx,By,Gx,Gy,Gst_x[3],Gst_y[3],G_n;
int dx[5]={1,-1,0,0},dy[5]={0,0,1,-1};
bool F[N][N],vis_B[N][N],vis_G[N][N];
queue<node> B,G;
char c;
bool check(int x,int y)
{if(x<1||x>n||y<1||y>m) return 0;return 1;
}
bool Catch(int x,int y,int dis)
{for(int i=1;i<=2;i++)if(abs(x-Gst_x[i])+abs(y-Gst_y[i])<=2*dis+2) return 1;  //鬼的曼哈顿距离return 0;
}
void pre()
{memset(vis_B,0,sizeof(vis_B));memset(vis_G,0,sizeof(vis_G));while(!B.empty()) B.pop();while(!G.empty()) G.pop();B.push((node){Bx,By,0});G.push((node){Gx,Gy,0});vis_B[Bx][By]=1;vis_G[Gx][Gy]=1;
}
inline int read() {int x=0,f=1;char s=getchar();while (s<'0'||s>'9') {if(s=='-') f=-f;s=getchar();}while (s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}return x*f;
}
bool bfs()
{pre();while(!B.empty()||!G.empty()){if(!G.empty())  //处理女孩行踪{int S=G.size();for(reg int k=1;k<=S;k++){qwq=G.front();G.pop();if(Catch(qwq.x,qwq.y,qwq.dis)) continue; //被抓for(int i=0;i<4;i++){int xx=qwq.x+dx[i];int yy=qwq.y+dy[i];if(check(xx,yy))if(!vis_G[xx][yy]&&F[xx][yy])  //未走&可走{if(!Catch(xx,yy,qwq.dis)&&vis_B[xx][yy])  //不会被抓&找到男孩{printf("%d\n",qwq.dis+1);return true;}vis_G[xx][yy]=1;  //标记G.push((node){xx,yy,qwq.dis+1});  //压入队列}}}}if(!B.empty())  //处理男孩行踪{for(int st=1;st<=3;st++)  //走3步{int S=B.size();for(reg int k=1;k<=S;k++){qwq=B.front();B.pop();if(Catch(qwq.x,qwq.y,qwq.dis)) continue;for(int i=0;i<4;i++){int xx=dx[i]+qwq.x;int yy=dy[i]+qwq.y;if(check(xx,yy))if(!vis_B[xx][yy]&&F[xx][yy]){if(!Catch(xx,yy,qwq.dis)&&vis_G[xx][yy]){printf("%d\n",qwq.dis+1);return true;}vis_B[xx][yy]=1;B.push((node){xx,yy,qwq.dis});}}}}int S=B.size();for(reg int k=1;k<=S;k++){qwq=B.front();B.pop();B.push((node){qwq.x,qwq.y,qwq.dis+1});  //算上1步}}}return 0;
}
int main(){T=read();while(T--){G_n=0;n=read();m=read();for(reg int i=1;i<=n;i++)for(reg int j=1;j<=m;j++){cin>>c;if(c=='.'||c=='M'||c=='G'){F[i][j]=1;if(c=='M'){Bx=i;By=j;}if(c=='G'){Gx=i;Gy=j;}  //男女坐标}if(c=='Z')  //鬼坐标{Gst_x[++G_n]=i;Gst_y[G_n]=j;  //有2个鬼F[i][j]=0;}if(c=='X') F[i][j]=0;  //墙体} if(bfs()==0) puts("-1");}		return 0; 
}