信息学奥赛一本通 1256：献给阿尔吉侬的花束 广度优先搜索算法
阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。字符S表示阿尔吉侬所在的位置，字符E表示奶酪所在的位置，字符#表示墙壁，字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。每组数据的输出结果占一行。每一组数据
1256：献给阿尔吉侬的花束
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。
迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置，字符E表示奶酪所在的位置，字符#表示墙壁，字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。
【输入】
第一行是一个正整数T（1 ≤ T ≤ 10），表示一共有T组数据。
每一组数据的第一行包含了两个用空格分开的正整数R和C（2 ≤ R, C ≤ 200），表示地图是一个R×C的矩阵。
接下来的R行描述了地图的具体内容，每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。
【输出】
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。每组数据的输出结果占一行。
【输入样例】
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.
【输出样例】
5
1
oop!
#include<bits/stdc++.h>
using namespace std;
int T;
int r,c;
char a[205][205];//地图
int sx,sy;//开始位置
struct node {
int x;//行坐标
int y;//列坐标
int step;//第几步
};
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void bfs(int x,int y){
queue <node> q;
node t;
t.x=x;
t.y=y;
t.step=0;
q.push(t);
while(!q.empty()){
t=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx=t.x+dx[i];
int yy=t.y+dy[i];
int step=t.step+1;
if (xx>=1&&xx<=r&&yy>=1&&yy<=c){
if (a[xx][yy]=='E'){
cout<<step<<endl;
return;
}
if (a[xx][yy]=='.'){
a[xx][yy]='#';
node tt;
tt.x=xx;
tt.y=yy;
tt.step=step;
q.push(tt);
}
}
}
}
cout<<"oop!"<<endl;
return;
}
int main(){
cin>>T;
while(T--){
cin>>r>>c;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
cin>>a[i][j];
if (a[i][j]=='S'){
sx=i;
sy=j;
}
}
}
bfs(sx,sy);
}
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
13
0- 0
已为社区贡献6条内容
所有评论(0)