概述
在我看来，每种算法都由两个部分组成，一部分是思想，另外一部分就是实现能力，二者缺一不可。缺少思想，算法就无法站住，或者可以说固定的模板无法和灵活的题目相联系。缺少实现能力，算法就成了空中楼阁，你想到的思路再清晰再高明，打不出来终究是心有余力不足。
在这篇博客中我将根据具体例题讲解部分bfs思路，正如上面所说，思想和实现能力是相辅相成的，我在这里理清了思路，还需要进行一个系列题目的练习，才能说把思路巩固了。如果有能力再进行高级的练习以及对于题目变形的解答。我希望在讲解的过程中也可以教学相长，如有错漏还请不吝赐教。
另外我有一些地方用到了结构体，不太明白的同学可以查一查，其实不难理解。
正文（例题）
洛谷 P1746 离开中山路
一个很简单的地图bfs
题目
https://www.luogu.org/problem/P1746
思路
一个字符型数组录入整张地图，然后从起始点出发。
我们以题目所给样例作解答。
按照样例我们来直观地画一张图：
此时我们建立一个队列数组，用来存放需要入队出队的位置，也就是被搜索到的位置，bfs不像dfs那样直接在dfs函数中调用，所以需要一个数组来决定它们执行搜索的先后顺序，我们也同样把这个队列数组画出来。
实现模拟队列的时候，与栈不同的是，队列需要两个变量，一个名叫head，一个叫tail，分别代表着队列的队头和队尾，只有队头和队尾中间才是队列的范围，当有数据需要入队，就令队尾自加，然后把数据加入，当有数据需要出队，则使队头自加即可。
那有的人就会说了，这样做数组的空间很浪费，所以才会出现了循环队列以及用链表实现的方法，这些暂时不会用到，所以仅在此提及一下。
接下来，我们来讲解这道题具体的bfs过程。
我们先把起始点[1][1]入队，此时的head和tail初始化都赋值为1。
此时开始只要head<=tail就不断循环调用bfs函数，从队列中的队头元素开始，对[1][1]这个点的四个方向进行枚举判断，发现仅右侧即[1][2]这个位置可以入队，故将该点入队。
随后此次bfs过程结束，我们把这次bfs搜索过的点出队。
按照如此的过程，把[2][2]这个位置入队。
然后到最后，按照我的代码思路，最后会是这样。
因为在执行[3][2]这个bfs的时候，向四周搜索会直接发现终点[3][3]，按照我的代码思路，此时应该将某个标记设置成1然后直接跳出，之后的过程由于某标记已经置1所以不用再执行了。而有些查找可能路径的题目则或许不用半路跳出，则只需等head>tail之后自动跳出循环即可。
另外在最终我们需要找出终点距起点的最短距离，那么我们只需要在每个点记录当前点的距离，然后对于每个由该点引出的，先前未被搜索过的点，只需将该距离加1即可。
如图。
当然在搜索过程中，已经搜索过的位置就不需要再次搜索了，因为在bfs过程中，某一个位置的最近到达所需距离就是它第一次被搜索到的时候的距离，多次搜索替换这个距离的话有可能造成错误，也浪费时间。
代码
#include<stdio.h>
int mapv[1005][1005]={0};
char map[1005][1005];
struct que
{
int x;
int y;
int sec;
}que[2000005];
int n;
int pd;
int head,tail;
int x1,y1,x2,y2;
int xa[5]={-1,0,1,0};
int ya[5]={0,-1,0,1};
void bfs(int q)
{
for(int i=0;i<=3;i++)
{
if((que[q].x+xa[i])>=0&&(que[q].x+xa[i])<=n-1&&(que[q].y+ya[i])>=0&&(que[q]. +ya[i])<=n-1)
{
if((que[q].x+xa[i])==x2-1&&(que[q].y+ya[i])==y2-1)
{
pd=1;
printf("%d\n",que[q].sec+1);
return;
}
if(mapv[que[q].x+xa[i]][que[q].y+ya[i]]==0&&map[que[q].x+xa[i]][que[q].y+ya[i]]=='0')
{
tail++;
que[tail].x=que[q].x+xa[i];
que[tail].y=que[q].y+ya[i];
que[tail].sec=que[q].sec+1;
mapv[que[q].x+xa[i]][que[q].y+ya[i]]=1;
}
}
}
}
int main()
{
head=1,tail=1;
pd=0;
scanf("%d",&n);
for(int i=0;i<=n-1;i++)
{
scanf("%s",map[i]);
}
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
que[1].x=x1-1;
que[1].y=y1-1;
que[1].sec=0;
if(x1==x2&&y1==y2)
{
printf("0");
return 0;
}
while(head<=tail)
{
bfs(head);
head++;
if(pd==1)
{
break;
}
}
return 0;
}
洛谷 P1443 马的遍历
对整张地图所有点进行搜索，找最短能到达的距离。
题目
https://www.luogu.org/problem/P1443
思路
棋盘上马走日，所以对于一般上下左右的四个点变成了另外的点。
有些点是走不到的，输出格式要求不能到达则输出-1，我们可以把记录整张地图最少步数的二维数组初始化为-1。另外题目要求左对齐，宽5格。
与普通的题目类似，只需不断进行bfs即可。
下面以题目样例为例讲解过程。
起始点是[1][1]，我们首先将该点入队，并且进行基本的初始化。
随后，对于该点可跳到的点进行枚举判断，随后tail自加两次并且分别入栈[2][3] [3][2]，[1][1]出队，head自加。
我们可以看到这两个新入队的点，步数都为1，都是由0+1得来的。
随后对队头元素([2][3])可跳到的点进行枚举判断。
[2][3]可以跳到[1][1]以及[3][1]这两个地图中的位置，但是由于[1][1]已经走过了，故不再入队，只将[3][1]入队，并且head自加，代表[2][3]这个点的bfs已经完成。
最后整个队列应该是这样子的。
随后head自加，再一次的循环中，head比tail大了，故能走到的点已经走完了，跳出了循环，地图上也已经打好了标记，没有走到的按照初始值是-1，这样就满足了题目的条件。
代码
#include<stdio.h>
int a[405][405];
int n,m;
int l=1;
int r=1;
int sx,sy;
int xa[10]={1,2,2,1,-1,-2,-2,-1};
int ya[10]={2,1,-1,-2,2,1,-1,-2};
struct b
{
int x1;
int y1;
int bu;
}b[40001];
void bfs(int x,int y,int bs)
{
for(int t=0;t<=7;t++)
{
if(a[x+xa[t]][y+ya[t]]==-1&&x+xa[t]>0&&x+xa[t]<n+1&&y+ya[t]>0&&y+ya[t]<m+1)
{
r++;
b[r].x1=x+xa[t];
b[r].y1=y+ya[t];
b[r].bu=bs+1;
a[x+xa[t]][y+ya[t]]=bs+1;
}
}
}
int main()
{
int i,j;
scanf("%d%d%d%d",&n,&m,&sx,&sy);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
a[i][j]=-1;
}
}
b[1].x1=sx;
b[1].y1=sy;
b[1].bu=0;
a[sx][sy]=0;
while(l<=r)
{
bfs(b[l].x1,b[l].y1,b[l].bu);
l++;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
printf("%-5d",a[i][j]);
}
printf("\n");
}
return 0;
}
洛谷 P1747 好奇怪的游戏
就是两遍bfs，并且一个点的可选点位变成了八个。
题目
https://www.luogu.org/problem/P1747
思路
这题当时做的时候没有太仔细想，我的做法就是一遍bfs之后把该初始化的全部初始化再进行一遍bfs。
具体bfs的实施过程也就是一个八个可能点位的普通地图bfs，就不在这里多说的，过程的话大概也都能明白。
代码
#include<stdio.h>
#include<string.h>
int mapw[30][30]={0};
int xa[15]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2};
int ya[15]={1,2,2,2,2,1,-1,-2,-2,-2,-2,-1};
int head,tail;
int pd;
struct que
{
int x1;
int y1;
int leap1;
}que[4005];
void bfs(int q)
{
for(int i=0;i<=11;i++)
{
if(que[q].x1+xa[i]==1&&que[q].y1+ya[i]==1)
{
pd=1;
printf("%d\n",que[q].leap1+1);
return;
}
if((que[q].x1+xa[i])>=1&&(que[q].x1+xa[i])<=20&&(que[q].y1+ya[i])>=1&&(que[q].y1+ya[i])<=20)
{
if(mapw[que[q].x1+xa[i]][que[q].y1+ya[i]]==0)
{
mapw[que[q].x1+xa[i]][que[q].y1+ya[i]]=1;
tail++;
que[tail].x1=que[q].x1+xa[i];
que[tail].y1=que[q].y1+ya[i];
que[tail].leap1=que[q].leap1+1;
}
}
}
}
int main()
{
int x[5];
int y[5];
scanf("%d%d%d%d",&x[1],&y[1],&x[2],&y[2]);
for(int t=1;t<=2;t++)
{
memset(mapw,0,sizeof(mapw));
head=1;
tail=1;
pd=0;
que[1].x1=x[t];
que[1].y1=y[t];
que[1].leap1=0;
if(x[t]==1&&y[t]==1)
{
printf("0\n");
continue;
}
while(head<=tail)
{
bfs(head);
head++;
if(pd==1)
{
break;
}
}
}
return 0;
}
洛谷 P1135 奇怪的电梯
这感觉上也算个地图型bfs了吧，我第一个打的bfs，思路可能有点乱，然后当时脑子也不咋清楚。
题目
https://www.luogu.org/problem/P1135
思路
就类地图型bfs，不同的是没有明显地图，然后每个点有两个选择。
另外和地图一样，这题目也是有边界的，需要谨慎处理这个边界的情况。
代码
#include<stdio.h>
int d[100005]; //bfs的层数组（队列）
int cs[100005]={0}; //第几次按电梯到达第i层
int c[205]; //第i层所记录的数字
int q[205]={0};
int gb[5]={-1,1};
int head,tail;
int a,b,n;
int pd=0;
void bfs(int ceng)
{
if(q[d[ceng]]==0)
{
q[d[ceng]]=1;
for(int i=0;i<=1;i++)
{
if(d[ceng]+gb[i]*c[d[ceng]]<=n&&d[ceng]+gb[i]*c[d[ceng]]>=1)
{
tail++;
d[tail]=d[ceng]+gb[i]*c[d[ceng]];
cs[tail]=cs[ceng]+1;
if(d[tail]==b)
{
pd=1;
return;
}
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
head=1;
tail=1;
q[a]=0;
d[1]=a;
cs[a]=0;
if(a==b)
{
printf("0");
return 0;
}
while(head<=tail)
{
bfs(head);
head++;
if(pd==1)
{
printf("%d",cs[tail]);
return 0;
}
}
printf("-1");
return 0;
}
洛谷 P1825 [USACO11OPEN]玉米田迷宫Corn Maze
在地图型bfs的基础上增加了传送门。
题目
https://www.luogu.org/problem/P1825
思路
看题可知，传送门只会成对出现，并且与二十六个大写英文字母一一对应，不会出现一个字母对应两组传送门的情况。
并且，传送门可以来回传送，但是这里有一个小坑，就是当你到达传送门所在位置的时候，必须执行传送操作，而你再想传送回来，则需要在对面的传送门向外走出一格再走回来。
当时写这道题的时候在这个坑这里倒了快一个小时，分析数据和结果分析出来的。
然后代码写得比较乱，看bfs函数里面的标记已走过位置的时候可能无法理解…反正看懂了大概思路就行，这些小细节因人而异。
代码
#include<stdio.h>
int mapv[505][505]={0};
char map[505][505];
int trans[255][5]={0};
struct que
{
int x;
int y;
int sec;
}que[500005];
int pd=0;
int m,n;
int begi,begj;
int head,tail;
int xa[5]={-1,0,1,0};
int ya[5]={0,-1,0,1};
void bfs(int q)
{
for(int i=0;i<=3;i++)
{
if((que[q].x+xa[i])>=0&&(que[q].x+xa[i])<=n-1&&(que[q].y+ya[i])>=0&&(que[q].y+ya[i])<=m-1)
{
if(map[que[q].x+xa[i]][que[q].y+ya[i]]=='=')
{
pd=1;
printf("%d\n",que[q].sec+1);
return;
}
if(mapv[que[q].x+xa[i]][que[q].y+ya[i]]==0&&map[que[q].x+xa[i]][que[q].y+ya[i]]!='#')
{
if(map[que[q].x+xa[i]][que[q].y+ya[i]]>='A'&&map[que[q].x+xa[i]][que[q].y+ya[i]]<='Z')
{
tail++;
if((que[q].x+xa[i]+1)*m+que[q].y+ya[i]==trans[map[que[q].x+xa[i]][que[q].y+ya[i]]][1])
{
que[tail].x=trans[map[que[q].x+xa[i]][que[q].y+ya[i]]][2]/m-1;
que[tail].y=trans[map[que[q].x+xa[i]][que[q].y+ya[i]]][2]%m;
que[tail].sec=que[q].sec+1;
}
else
{
que[tail].x=trans[map[que[q].x+xa[i]][que[q].y+ya[i]]][1]/m-1;
que[tail].y=trans[map[que[q].x+xa[i]][que[q].y+ya[i]]][1]%m;
que[tail].sec=que[q].sec+1;
}
que[tail].sec=que[q].sec+1;
}
else
{
tail++;
que[tail].x=que[q].x+xa[i];
que[tail].y=que[q].y+ya[i];
que[tail].sec=que[q].sec+1;
mapv[que[q].x+xa[i]][que[q].y+ya[i]]=1;
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n-1;i++)
{
scanf("%s",map[i]);
}
for(int i=0;i<=n-1;i++)
{
for(int j=0;j<=m-1;j++)
{
if(map[i][j]=='@')
{
begi=i;
begj=j;
}
if(map[i][j]>='A'&&map[i][j]<='Z')
{
if(trans[map[i][j]][1]==0)
{
trans[map[i][j]][1]=(i+1)*m+j;
}
else
{
trans[map[i][j]][2]=(i+1)*m+j;
}
}
}
}
head=1,tail=1;
que[1].x=begi;
que[1].y=begj;
que[1].sec=0;
mapv[begi][begj]=1;
while(head<=tail)
{
bfs(head);
head++;
if(pd==1)
{
break;
}
}
return 0;
}
洛谷 P1126 机器人搬重物
这个题目的设置，包括每一步可走的点，以及这些点所能遇到的情况都非常复杂，当时打了一遍出来a了一半的点，改了一次又a了一半的一半，最后才改对。
题目
https://www.luogu.org/problem/P1126
思路
首先，题目中提及机器人的形状是直径1.6m的球，然后机器人在格点上行走。而在地图上给出的黑色位置，实际上会占据四个格点。这就需要我们在录入地图的时候做出一些巧妙的变化。
此处搬一下题解里雒仁韬大佬所画的图（我不认识这位大佬，如果大佬觉得搬图侵权啥的我可以删掉）
其次，机器人可以朝面前方向行走一格两格或者三格，但是这都是在前方没有不能行走的格点的情况下，如果行走三格，就要看看前方两格三格的地方有没有障碍物。
另外，贮藏室，也就是整张地图的外围一圈是有墙体的，这点在上面那位大佬的图中也有体现。
最后，普通bfs对于每个格子打上标记，而我写这道题是对每个格子的每个方向都打上标记。我写的代码有四百行，因为其中包含着很多的判断分支，肯定是可以简化的，也会有简单一些的办法，或者说查看一下大佬们的解法都可以。
代码
#include<stdio.h>
int mak[55][55][5]={0};
int head,tail;
int a,b,c,d;
int jud=0;
int n,m;
struct que
{
int x;
int y;
int sec;
int fx; //方向：0 上 1 右 2 下 3 左
}que[50005];
void bfs(int ceng)
{
for(int i=1;i<=5;i++) //4:向右 5:向左
{
switch(i)
{
case 1:
{
switch(que[ceng].fx)
{
case 0:
{
if(que[ceng].x-1>=1)
{
if(mak[que[ceng].x-1][que[ceng].y][que[ceng].fx]==0)
{
tail++;
que[tail].x=que[ceng].x-1;
que[tail].y=que[ceng].y;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
case 1:
{
if(que[ceng].y+1<=m+1)
{
if(mak[que[ceng].x][que[ceng].y+1][que[ceng].fx]==0)
{
tail++;
que[tail].x=que[ceng].x;
que[tail].y=que[ceng].y+1;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
case 2:
{
if(que[ceng].x+1<=n+1)
{
if(mak[que[ceng].x+1][que[ceng].y][que[ceng].fx]==0)
{
tail++;
que[tail].x=que[ceng].x+1;
que[tail].y=que[ceng].y;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
case 3:
{
if(que[ceng].y-1>=1)
{
if(mak[que[ceng].x][que[ceng].y-1][que[ceng].fx]==0)
{
tail++;
que[tail].x=que[ceng].x;
que[tail].y=que[ceng].y-1;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
}
}
break;
case 2:
{
switch(que[ceng].fx)
{
case 0:
{
if(que[ceng].x-2>=1)
{
if(mak[que[ceng].x-2][que[ceng].y][que[ceng].fx]==0&&mak[que[ceng].x-1][que[ceng].y][que[ceng].fx]!=1)
{
tail++;
que[tail].x=que[ceng].x-2;
que[tail].y=que[ceng].y;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
case 1:
{
if(que[ceng].y+2<=m+1)
{
if(mak[que[ceng].x][que[ceng].y+2][que[ceng].fx]==0&&mak[que[ceng].x][que[ceng].y+1][que[ceng].fx]!=1)
{
tail++;
que[tail].x=que[ceng].x;
que[tail].y=que[ceng].y+2;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
case 2:
{
if(que[ceng].x+2<=n+1)
{
if(mak[que[ceng].x+2][que[ceng].y][que[ceng].fx]==0&&mak[que[ceng].x+1][que[ceng].y][que[ceng].fx]!=1)
{
tail++;
que[tail].x=que[ceng].x+2;
que[tail].y=que[ceng].y;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
case 3:
{
if(que[ceng].y-2>=1)
{
if(mak[que[ceng].x][que[ceng].y-2][que[ceng].fx]==0&&mak[que[ceng].x][que[ceng].y-1][que[ceng].fx]!=1)
{
tail++;
que[tail].x=que[ceng].x;
que[tail].y=que[ceng].y-2;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
}
}
break;
case 3:
{
switch(que[ceng].fx)
{
case 0:
{
if(que[ceng].x-3>=1)
{
if(mak[que[ceng].x-3][que[ceng].y][que[ceng].fx]==0&&mak[que[ceng].x-2][que[ceng].y][que[ceng].fx]!=1&&mak[que[ceng].x-1][que[ceng].y][que[ceng].fx]!=1)
{
tail++;
que[tail].x=que[ceng].x-3;
que[tail].y=que[ceng].y;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
case 1:
{
if(que[ceng].y+3<=m+1)
{
if(mak[que[ceng].x][que[ceng].y+3][que[ceng].fx]==0&&mak[que[ceng].x][que[ceng].y+2][que[ceng].fx]!=1&&mak[que[ceng].x][que[ceng].y+1][que[ceng].fx]!=1)
{
tail++;
que[tail].x=que[ceng].x;
que[tail].y=que[ceng].y+3;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
case 2:
{
if(que[ceng].x+3<=n+1)
{
if(mak[que[ceng].x+3][que[ceng].y][que[ceng].fx]==0&&mak[que[ceng].x+2][que[ceng].y][que[ceng].fx]!=1&&mak[que[ceng].x+1][que[ceng].y][que[ceng].fx]!=1)
{
tail++;
que[tail].x=que[ceng].x+3;
que[tail].y=que[ceng].y;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
case 3:
{
if(que[ceng].y-3>=1)
{
if(mak[que[ceng].x][que[ceng].y-3][que[ceng].fx]==0&&mak[que[ceng].x][que[ceng].y-2][que[ceng].fx]!=1&&mak[que[ceng].x][que[ceng].y-1][que[ceng].fx]!=1)
{
tail++;
que[tail].x=que[ceng].x;
que[tail].y=que[ceng].y-3;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx;
if(que[tail].x==c&&que[tail].y==d)
{
jud=1;
printf("%d\n",que[tail].sec);
}
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
}
break;
}
}
break;
case 4:
{
if(mak[que[ceng].x][que[ceng].y][(que[ceng].fx+1)%4]==0)
{
tail++;
que[tail].x=que[ceng].x;
que[tail].y=que[ceng].y;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx+1;
que[tail].fx%=4;
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
break;
case 5:
{
if(mak[que[ceng].x][que[ceng].y][(que[ceng].fx+3)%4]==0)
{
tail++;
que[tail].x=que[ceng].x;
que[tail].y=que[ceng].y;
que[tail].sec=que[ceng].sec+1;
que[tail].fx=que[ceng].fx+3;
que[tail].fx%=4;
mak[que[tail].x][que[tail].y][que[tail].fx]=2;
}
}
break;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int k;
char e;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&k);
if(k==1)
{
for(int q=0;q<=3;q++)
{
mak[i][j][q]=1;
mak[i][j+1][q]=1;
mak[i+1][j][q]=1;
mak[i+1][j+1][q]=1;
}
}
}
}
for(int i=1;i<=n+1;i++)
{
for(int q=0;q<=3;q++)
{
mak[i][1][q]=1;
mak[i][m+1][q]=1;
}
}
for(int j=1;j<=m+1;j++)
{
for(int q=0;q<=3;q++)
{
mak[1][j][q]=1;
mak[n+1][j][q]=1;
}
}
scanf("%d%d%d%d %c",&a,&b,&c,&d,&e);
head=1;
tail=1;
a+=1;
b+=1;
c+=1;
d+=1;
if(a==c&&b==d)
{
printf("0");
return 0;
}
que[head].x=a;
que[head].y=b;
que[head].sec=0;
switch(e)
{
case 'N':que[head].fx=0;
break;
case 'E':que[head].fx=1;
break;
case 'S':que[head].fx=2;
break;
case 'W':que[head].fx=3;
break;
}
mak[a][b][que[head].fx]=1;
while(head<=tail)
{
bfs(head);
head++;
if(jud==1) //下一步已经试探出终点
{
break;
}
}
if(jud==0)
{
printf("-1");
}
return 0;
}
洛谷 P1902 刺杀大使
题目
https://www.luogu.org/problem/P1902
思路
二分答案+bfs能否到达
未完待续……
代码
#include<stdio.h>
#define MAX 10005
int v[1005][1005]={0};
struct que
{
int x1;
int y1;
}que[1000005];
int xa[5]={0,-1,0,1};
int ya[5]={-1,0,1,0};
int a[1005][1005];
int head,tail;
int r,l;
int pd;
int m,n;
int mid;
void bfs(int x,int y)
{
for(int i=0;i<=3;i++)
{
if(x+xa[i]<=n&&x+xa[i]>=1&&y+ya[i]<=m&&y+ya[i]>=1)
{
if(v[x+xa[i]][y+ya[i]]==0)
{
if(x+xa[i]==n)
{
pd=1;
}
v[x+xa[i]][y+ya[i]]=1;
tail++;
que[tail].x1=x+xa[i];
que[tail].y1=y+ya[i];
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
r=1000;
l=0;
while(r>=l)
{
head=1,tail=1;
pd=0;
mid=(r+l)/2;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]>mid)
{
v[i][j]=1;
}
else
{
v[i][j]=0;
}
}
}
que[1].x1=1;
que[1].y1=1;
while(head<=tail)
{
bfs(que[head].x1,que[head].y1);
head++;
if(pd==1)
{
break;
}
}
if(pd==1)
{
r=mid-1;
}
else
{
l=mid+1;
}
}
printf("%d",r+1);
return 0;
}
未完待续
Author: Maple
Link: http://www.unknown9t.com/2022/04/29/bfs%E4%B9%A0%E9%A2%98%E8%AE%B2%E8%A7%A3/
Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.