Bfs68分求调
  • 板块P2802 回家
  • 楼主liaomingtao
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/17 19:19
  • 上次更新2024/10/17 20:49:55
查看原帖
Bfs68分求调
607215
liaomingtao楼主2024/10/17 19:19
#include<bits/stdc++.h>
using namespace std;
int n,m,mp[105][105],startx,starty,endx,endy;
struct Item{
	int x;
	int y;
	int step;
	int hp;
};
void start(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]==2){
				startx=i;
				starty=j;
			}
			if(mp[i][j]==3){
				endx=i;
				endy=j;
			}
		}
	}
}
int bfs(){
	queue<Item> q;
	q.push({startx,starty,0,6});
	mp[startx][starty]=0;
	while(!q.empty()){
		Item carry=q.front();
		q.pop();
		for(int i=1;i<=4;i++){
			Item next=carry;
			if(i==1){
				next.x++;
				next.step++;
				next.hp--;
			}
			if(i==2){
				next.x--;
				next.step++;
				next.hp--;
			}
			if(i==3){
				next.y--;
				next.step++;
				next.hp--;
			}
			if(i==4){
				next.y++;
				next.step++;
				next.hp--;
			}
			if(next.hp<=0){
				break;
			}
			if(mp[next.x][next.y]==4){
				next.hp=6;
			}
			if(mp[next.x][next.y]==1){
				q.push(next);
				mp[next.x][next.y]=0;
			}
			if(next.x==endx&&next.y==endy){
				return next.step;
			}
		}
	}
	return -1;
}
int main(){
	cin>>n>>m;
	fill(mp[0],mp[15],0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}
	start();
	cout<<bfs();
	return 0;
}
2024/10/17 19:19
加载中...