AcWing 1101. 献给阿尔吉侬的花束
原题链接
简单
作者:
LBAC
,
2024-03-17 01:19:43
,
所有人可见
,
阅读 15
bfs
献给阿尔吉侬的花束
#include <iostream>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
const int N = 210;
typedef pair<int,int> PII;
int r,c;
char g[N][N];
int dis[N][N];
PII start; //记录起点
void bfs(PII start){
queue<PII> q; //创建队列
q.push(start); //入队
//对队列进行循环遍历,不断得出队入队
while(!q.empty()){ //判断队列非空
PII u = q.front(); //取队头元素
q.pop(); //出队
//具体行为逻辑
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
for(int i=0;i<4;i++){
int x = u.first + dx[i];
int y = u.second + dy[i];
if(x>=0 && x<r && y>=0 && y<c){ //判断是否超出边界
if(g[x][y] == '#') continue;
if(dis[x][y] !=0 ) continue; //距离非0代表这个点已经遍历过了,所以跳过
if(g[x][y] == '.'){
dis[x][y] = dis[u.first][u.second] + 1;
// g[x][y] = '#'; //代表遍历过的点不要再重复遍历了
q.push({x,y});
}
if(g[x][y] == 'E'){
cout << dis[u.first][u.second] + 1 << endl;
return;
}
}
}
}
cout << "oop!" << endl; //没找到
}
int main(){
int T;
cin >> T;
while(T--){
//每次新的循环时需要初始化距离数组为0,防止造成数据污染
memset(dis, 0, sizeof(dis));//初始化dis
cin >> r >> c;
//输入矩阵数据
for(int i=0; i<r; i++){
for(int j=0; j<c;j++){
cin >> g[i][j];
if(g[i][j] == 'S'){
start.first = i;
start.second = j;
}
}
}
//开始行动
bfs(start);
}
return 0;
}