献给阿尔吉侬的花束🌸
BFS
解题流程:
- 以g[N][N]二维数组
存放迷宫
,
- 二维数组遍历出起点终点,并
保存,且作为BFS的参数传递
- 设置同地图一样大小的dist[N][N}数组
目的用于判重和存放从起点到此位置的最短距离
- 用
二元组队列
来扩展BFS的做法,并设置出口优化
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define N 210
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
char g[N][N];
int dist[N][N];//既可以判重,又可以保存距离
int m,n;
int bfs(PII start,PII end)
{
queue<PII> q;
//先初始化dist数组为-1
memset(dist , -1 , sizeof dist);
//初始化起点,起点即为当前已经走过的点
dist[start.x][start.y] = 0;
q.push(start);
int dx[] = {-1,0,1,0} , dy[] = {0,1,0,-1};
while(q.size())
{
PII t = q.front();
q.pop();
for(int i = 0;i < 4;i ++)
{
int a = t.x + dx[i] , b = t.y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] == '#')
continue;//越界撞墙都不过!
if(dist[a][b] != -1)
continue;//再看是否走过!
//通过判断更新dist[t.x][t.y] + 1;
dist[a][b] = dist[t.x][t.y] + 1;
//判断是否为终点
if(end == make_pair(a,b))
return dist[a][b];
//并将a,b入队
q.push({a,b});
}
}
return -1;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i = 0;i < n;i ++) scanf("%s",g[i]);
PII start,end;
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
if(g[i][j] == 'S') start = {i,j};
else if(g[i][j] == 'E') end = {i,j};
int distance = bfs(start, end);
if(distance == -1) puts("oop!");
else printf("%d\n",distance);
}
return 0;
}
精益求精!
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define x first
#define y second
#define N 210
using namespace std;
typedef pair<int,int> PII;
char g[N][N];
int dist[N][N];
int n,m;
int dx[4] = {-1,0,1,0},dy[4] = {0,-1,0,1};
void bfs(PII start)
{
queue<PII> q;
memset(dist,-1,sizeof dist);
dist[start.x][start.y] = 0;
q.push(start);
while(q.size())
{
auto t = q.front(); q.pop();
for(int i = 0;i < 4;i ++)
{
int a = t.x + dx[i] , b = t.y + dy[i];
if(a < 0||a >= n||b < 0||b >= m||dist[a][b] != -1||g[a][b] == '#')
continue;
dist[a][b] = dist[t.x][t.y] + 1;
if(g[a][b] == 'E')
{
printf("%d\n",dist[a][b]);
return;
}
q.push({a,b});
}
}
printf("oop!\n");
}
int main()
{
int T;
scanf("%d",&T);
while(T --)
{
PII start;
scanf("%d %d",&n,&m);
for(int i = 0;i < n;i ++) scanf("%s",g[i]);
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
if(g[i][j] == 'S') start = {i,j};
bfs(start);
}
}