当前位置:网站首页>1256:献给阿尔吉侬的花束
1256:献给阿尔吉侬的花束
2022-04-23 13:58:00 【暴揍键盘的程序猿】
1256:献给阿尔吉侬的花束
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 9651 通过数: 4023
【题目描述】
阿尔吉侬是一只聪明又慵懒的小白鼠,它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫,研究员们为了鼓励阿尔吉侬尽快到达终点,就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道,如果阿尔吉侬足够聪明,它最少需要多少时间就能吃到奶酪。
迷宫用一个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!
【AC代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
const int INF=0x3f3f3f3f;
inline int read()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0'||ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
void write(int n)
{
if(n>9)write(n/10);
putchar(n%10+'0');
}
int t,r,c,sx,sy,dir[4][2]={
{-1,0},{1,0},{0,-1},{0,1}};
char m[N][N];
bool vis[N][N];
struct point
{
int px,py,pt;
};
queue<point> q;
void bfs(int tx,int ty,int tt)
{
q.push((point){tx,ty,tt});
vis[tx][ty]=1;
while(!q.empty())
{
point p=q.front();
q.pop();
if(m[p.px][p.py]=='E')
{
cout<<p.pt<<"\n";
return;
}
for(int i=0;i<4;i++)
{
int nx=p.px+dir[i][0],ny=p.py+dir[i][1];
if(nx>0&&nx<=r&&ny>0&&ny<=c&&m[nx][ny]!='#'&&vis[nx][ny]==0)
{
q.push((point){nx,ny,p.pt+1});
vis[nx][ny]=1;
}
}
}
cout<<"oop!\n";
}
int main(int argc,char **argv)
{
t=read();
while(t--)
{
r=read(),c=read();
memset(vis,0,sizeof vis);
memset(m,'\0',sizeof m);
while(!q.empty())q.pop();
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
cin>>m[i][j];
if(m[i][j]=='S')sx=i,sy=j;
}
bfs(sx,sy,0);
}
return 0;
}
版权声明
本文为[暴揍键盘的程序猿]所创,转载请带上原文链接,感谢
https://blog.csdn.net/Xiaorui_xuan/article/details/124353457
边栏推荐
- Analysis of cluster component gpnp failed to start successfully in RAC environment
- Spark入门基本操作
- Leetcode brush question 897 incremental sequential search tree
- Function executes only the once function for the first time
- cnpm的诡异bug
- Quartus Prime硬件实验开发(DE2-115板)实验二功能可调综合计时器设计
- Apache seatunnel 2.1.0 deployment and stepping on the pit
- Search ideas and cases of large amount of Oracle redo log
- 自动化的艺术
- Small case of web login (including verification code login)
猜你喜欢
Elmo (bilstm-crf + Elmo) (conll-2003 named entity recognition NER)
Reading notes: meta matrix factorization for federated rating predictions
UML Unified Modeling Language
Detailed explanation of redis (Basic + data type + transaction + persistence + publish and subscribe + master-slave replication + sentinel + cache penetration, breakdown and avalanche)
PG SQL intercepts the string to the specified character position
Kettle--控件解析
Android 面试主题集合整理
Leetcode brush question 897 incremental sequential search tree
The art of automation
【报名】TF54:工程师成长地图与卓越研发组织打造
随机推荐
10g database cannot be started when using large memory host
村上春树 --《当我谈跑步时,我谈些什么》句子摘录
33 million IOPs, 39 microsecond delay, carbon footprint certification, who is serious?
[code analysis (7)] communication efficient learning of deep networks from decentralized data
Jenkins construction and use
Move blog to CSDN
Jiannanchun understood the word game
ACFs file system creation, expansion, reduction and other configuration steps
Three characteristics of volatile keyword [data visibility, prohibition of instruction rearrangement and no guarantee of operation atomicity]
L2-024 部落 (25 分)
UML Unified Modeling Language
Postman reference summary
[code analysis (4)] communication efficient learning of deep networks from decentralized data
Tensorflow Download
Force deduction brush question 101 Symmetric binary tree
[code analysis (2)] communication efficient learning of deep networks from decentralized data
UML统一建模语言
Oracle RAC database instance startup exception analysis IPC send timeout
Dolphin scheduler integrates Flink task pit records
Detailed explanation of redis (Basic + data type + transaction + persistence + publish and subscribe + master-slave replication + sentinel + cache penetration, breakdown and avalanche)