BFS 64'(WA 1#10#11#12#)
  • 板块P2802 回家
  • 楼主yaoshuen
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/6/12 20:29
  • 上次更新2023/10/23 13:16:15
查看原帖
BFS 64'(WA 1#10#11#12#)
916086
yaoshuen楼主2023/6/12 20:29
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[21][21];
struct node{
	int x;
	int y;
	int ti;
	int hp;
};
queue<node>q;
int x,y,tx,ty,hp,ti;
int sx,sy,ex,ey;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
bool h[21][21];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]==2) a[i][j]=1,sx=i,sy=j;
			else if(a[i][j]==3) a[i][j]=1,ex=i,ey=j;
		}
	}
	q.push(node{sx,sy,0,6});
	while(!q.empty()){
		x=q.front().x;
		y=q.front().y;
		ti=q.front().ti;
		hp=q.front().hp;
		q.pop();
		if(x==ex&&y==ey){
			printf("%d",ti);
			exit(0);
		}
		for(int i=0;i<4;i++){
			tx=x+dx[i];
			ty=y+dy[i];
			if(tx>0&&tx<=n&&ty>0&&ty<=m&&a[tx][ty]!=0&&hp>0&&!h[tx][ty]){
				h[tx][ty]=1;
				if(a[tx][ty]==1){
					q.push(node{tx,ty,ti+1,hp-1});
				}
				else if(a[tx][ty]==4){
					q.push(node{tx,ty,ti+1,6});
				}
			}
		}
	}
	printf("-1");
	return 0;
}

2023/6/12 20:29
加载中...