社区讨论
性感蒟蒻90分在线求助!
P2802回家参与者 12已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @mi860ks1
- 此快照首次捕获于
- 2025/11/21 09:12 4 个月前
- 此快照最后确认于
- 2025/11/21 09:47 4 个月前
我这个代码哪里有问题(虽然确实错了)!
虽然我知道应该是DFS,但是我更习惯于BFS.
求大佬查错,三克油.
CPP/*
=======
by:AsianGiao
time:2019.7.5
=======
BFS寻求最佳路径,类似于走迷宫,血量起始为6
但是每走一步都会消耗血量,血量为0即为死亡
但是也可以拾取鼠标(??)来补充血量,直接补满
迷宫中的0代表障碍物,是不可以走的
迷宫中的1是空地,可以自由走
迷宫中的2是出发地
迷宫中的3是目的地(家)
迷宫中的4是可以补血的地方
*/
#include <cstdio>
#include <iostream>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstring>
#define N 12
#define LL long long
using namespace std;
inline int read()
{
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
struct node
{
int x,y,HP,step;
};
const int max_HP=6;
queue<node>q;
int g[N][N],vis[N][N]={0},n,m,ans=0,flag=0;
int xx[4]={0,1,0,-1};
int yy[4]={1,0,-1,0};
void BFS(int x,int y)
{
node now,net;
now.x=x,now.y=y,now.step=0,now.HP=6;
vis[x][y]=1;
q.push(now);
while(!q.empty()) {
now = q.front();
q.pop();
x = now.x , y = now.y ;
ans=now.step;
int hp=now.HP;
if(hp<=0)
continue;
if(g[x][y]==3) {
flag = 1 ;
break;
}
if(g[x][y]==4)
hp=max_HP;
for(int i = 0 ; i < 4 ; ++ i) {
int dx = x + xx[i] ;
int dy = y + yy[i] ;
if(g[dx][dy]!=0&&dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy]) {
vis[dx][dy]=1;
net.HP=hp-1;
net.step=ans+1;
net.x=dx;net.y=dy;
q.push(net);
}
}
}
if(flag==1)
printf("%d",ans);
else
printf("-1");
}
int main()
{
// freopen("home.in","r",stdin);
// freopen("home.out","w",stdout);
int dx,dy;
n=read();m=read();
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j) {
g[i][j] = read();
if(g[i][j]==2)
dx=i,dy=j;
}
BFS(dx,dy);
return 0;
}
这个是错的测试点:
CPP输入
8 4
3 1 1 1
1 1 1 0
1 1 1 1
0 1 1 2
1 4 4 1
1 4 0 1
1 0 1 1
1 0 1 1
CPP输出
8
回复
共 15 条回复,欢迎继续交流。
正在加载回复...