广搜
用大脑去模拟广搜真的很难。(兴许是我大脑运行内存低?)
它并不像是深搜那样一步到位然后尝试另外一个分支,而这个更像是流水线一样一套一套的答案一起做好。
举个例子就是深搜就是奇异博士里时间宝石尝试多种可能找出答案。
而这个则是改一个分支则存一个档改一个分支存一个档。(玩过gal的同学应该很熟悉)
广搜解决最短路这样的问题真的比深搜好用太多了,因为深搜做这样的题目很容易TLE。
关于遍历我的代码就是东南西北。
遍历方向最好是一直写一种不然两个数组没同步那就找半年都找不出错误了。
像是以前写过FX是东南西北而FY是左上右下。。。。
代码
#include<queue>
#include<cstdio>
using namespace std;
const int sz=101;
int n,m,i,j,x,y,tx,ty,a[sz][sz],s,d[sz][sz];
queue<pair<int,int> >q;
int fx[4]={1,0,-1,0},fy[4]={0,1,0,-1};
int main()
{
scanf("%d%d",&n,&m);q.push({1,1});
for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&a[i][j]);
while(q.size())
{
x=q.front().first;y=q.front().second;q.pop();
for(i=0;i<4;++i)
{
tx=x+fx[i];ty=y+fy[i];
if(tx>0&&tx<=n&&ty>0&&ty<=m&&!a[tx][ty]&&!d[tx][ty])d[tx][ty]=d[x][y]+1,q.push({tx,ty});
if(tx==n&&ty==m){printf("%d",d[n][m]);return 0;}
}
}
return 0;
}
复习搜索递归发现还有很多不会的但是这种模板广搜依旧还是容易的。