90分求助
  • 板块P2802 回家
  • 楼主_caiji_
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/2/28 19:13
  • 上次更新2023/11/5 02:34:58
查看原帖
90分求助
390033
_caiji_楼主2021/2/28 19:13

rt,用的 dfs。

#include <cstdio>
using namespace std;
#define min vcbdkjuvflkiureouk
int min(int a,int b){return a<b?a:b;}
const int dx[]={0,-1,0,0,1},
		  dy[]={0,0,-1,1,0};
int n,m,a[110][110],sx,sy,ex,ey,ans=0x3f3f3f3f;
bool vis[110][110];
bool checkp(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=m;}
void dfs(int x,int y,int hp,int t){
	if(x==ex&&y==ey) return (void)(ans=min(ans,t));
	if(hp==0||hp==1) return ;
	for(int i=1;i<=4;i++){
		int tmpx=x+dx[i],tmpy=y+dy[i];
		if(checkp(tmpx,tmpy)&&!vis[tmpx][tmpy]&&a[tmpx][tmpy]!=0){
			vis[tmpx][tmpy]=1;
			if(a[tmpx][tmpy]==4) (hp!=1)&&(dfs(tmpx,tmpy,6,t+1),1);
			else dfs(tmpx,tmpy,hp-1,t+1);
			vis[tmpx][tmpy]=0;
		}
	}
}
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]),
			(a[i][j]==2)&&(sx=i,sy=j,a[i][j]=1),
			(a[i][j]==3)&&(ex=i,ey=j,a[i][j]=1);
	dfs(sx,sy,6,0);
	printf("%d",ans==0x3f3f3f3f?-1:ans);
	return 0;
}
2021/2/28 19:13
加载中...