走迷宫
这题目大家应该蛮熟悉,然后我隔了很久之后想来再写一下。的确很容易AC,但是我对比了一下之前的代码,曾一度认为是数据有点问题,不过仔细思索之后发现了一些小细节。特此记录。
有什么问题呢?我们都知道说,由某一步转移到下一步要满足这样几个条件:1.合法,就是说不能超出范围;2.没进入过队列或者说没被访问。3.根据初始矩阵判断该位置能否被访问。
那么来看第一份代码
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=105;
int n,m,dist[N][N];
bool sta[N][N];
int change[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
typedef pair<int,int> PII;
PII q[N*N];
int tt=-1,hh=0;
void bfs(int x,int y)
{
dist[1][1]=0;
q[++tt]={1,1};
int x_old,y_old,x_new,y_new;
while(hh<=tt)
{
x_old=q[hh].first;
y_old=q[hh].second;
hh++;
for(int i=0;i<4;i++)
{
x_new=x_old+change[i][0];
y_new=y_old+change[i][1];
if(!sta[x_new][y_new] && dist[x_new][y_new]==-1)
{
dist[x_new][y_new]=dist[x_old][y_old]+1;
q[++tt]={x_new,y_new};
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&sta[i][j]);
dist[i][j]=-1;
}
}
bfs(1,1);
printf("%d\n",dist[n][m]);
return 0;
}
这一段代码是很早之前写的以至于我都忘记了他的细节。乍一看可能会发现他在更新距离的之前并没判断新位置合法不合法。 if(!sta[x_new][y_new] && dist[x_new][y_new]==-1)
他只判断了是否被访问过以及能否被访问,并没有判断是否合法。
细节之处在于初始化的时候没有用memset,只有合法的(1,1)~(n,m)的位置被初始化了,那么当更新新位置的时候,最多只会计算到周围一圈不合法的位置作为候选,但由于类似(0,1)这样的位置由于dist没被初始化,即便候选也无法进入队列,从而保证了不会出现数组越界的情况。
再来看第二份,新鲜出炉的
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
bool st[N][N];
int dis[N][N],n,m;
int change[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
void bfs()
{
queue<PII> q;
q.push({1,1});
st[1][1]=true;
dis[1][1]=0;
PII head;
int x,xx,y,yy;
while(q.size())
{
head=q.front();
q.pop();
x=head.first;
y=head.second;
for(int i=0;i<4;i++)
{
xx=x+change[i][0];
yy=y+change[i][1];
if(xx>=1 && xx<=n && yy>=1 && yy<=m && !st[xx][yy])
{
q.push({xx,yy});
st[xx][yy]=true;
dis[xx][yy]=dis[x][y]+1;
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cin>>st[i][j];
bfs();
cout<<dis[n][m];
return 0;
}
你会发现这里好像只判了是否合法和能否被访问,似乎并没有判断是否被访问过或者说是否进入过队列 if(xx>=1 && xx<=n && yy>=1 && yy<=m && !st[xx][yy])