社区讨论

性感蒟蒻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 条回复,欢迎继续交流。

正在加载回复...