社区讨论
求助
学术版参与者 6已保存回复 18
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 18 条
- 当前快照
- 1 份
- 快照标识符
- @mi7yarsw
- 此快照首次捕获于
- 2025/11/21 05:36 4 个月前
- 此快照最后确认于
- 2025/11/21 06:42 4 个月前
我们一场考试的题目,快结束了,已经放弃的我决定求助各位大神
CPPProblem I
Problem Description
Rabbit在晚上回家的时候因为天太黑看不清路,陷入了一个迷宫里,她只能无助地留在原地等待救援。
由于Rabbit有很多粉丝,他们知道后立马展开了营救。
粉丝每一分钟可以上下左右移动一个位置,但是不能走出迷宫。
Rabbit想知道自己最快多久能被找到。
Input
输入数据第一行为T,表示数据组数。(1<=T<=100)
每组第一行为两个数n,m,表示迷宫的大小。(1<=n,m<=200)
接下来n行,每行m个字符。'.'表示可以走的点,'#'表示不可以走的点,'R'表示Rabbit所在的位置,每个'F'表示Rabbit的粉丝的起始位置。
Output
对于每组数据,如果Rabbit能被安全找到,输出最小时间。
否则输出"Poor Rabbit."
Sample Input
1
3 4
#.R#
F#..
....
Sample Output
5
CPP//T9
#include<bits/stdc++.h>
using namespace std;
char mapp[205][205];
bool vis[205][205];
int T,minn,n,m,sx,sy;
int qx[]={0,0,-1,1},qy[]={-1,1,0,0};
void dfs(int x,int y,int step)
{
if(mapp[x][y]=='F')
{
if(step<minn)
{
minn=step;
}
return;
}
for(int i=0;i<4;i++)
{
int xx=x+qx[i];
int yy=y+qy[i];
if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&mapp[xx][yy]!='#'&&vis[xx][yy]==0)
{
vis[xx][yy]=1;
dfs(xx,yy,step+1);
vis[xx][yy]=0;
}
}
}
int main()
{
std::cin>>T;
while(T--)
{
std::cin>>n>>m;
memset(mapp,0,sizeof(mapp));
memset(vis,0,sizeof(vis));
minn=1000000;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
std::cin>>mapp[i][j];
if(mapp[i][j]=='R')
{
sx=i;
sy=j;
}
}
}
dfs(sx,sy,0);
vis[sx][sy]=1;
if(minn==1000000)
{
std::cout<<"Poor Rabbit.\n";
}
else
{
std::cout<<minn<<endl;
}
}
}
最好还是深搜(TLE了)
回复
共 18 条回复,欢迎继续交流。
正在加载回复...