40分其他MLE求助
  • 板块P2802 回家
  • 楼主CCK_demon
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/11 21:44
  • 上次更新2024/4/12 11:25:48
查看原帖
40分其他MLE求助
782554
CCK_demon楼主2024/4/11 21:44
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[15][15];//地图
int ans=2e9+5;//答案
int sx,sy,ex,ey,n,m;//出发点坐标,终点坐标,地图大小
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
void dfs(int x,int y,int sum,int health)//当前坐标,步数,生命值
{
	if(sum>ans)
	{
		return ;
	}
	if(health<=0)
	{
		return ;
	}
	if(a[x][y]==4)
	{
		health=6;
	}
	if(x==ex&&y==ey)
	{
		ans=min(ans,sum);
		return ;
	}
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<=0||nx>n||ny<=0||ny>m||a[nx][ny]==0)
		{
			continue ;
		}
		dfs(nx,ny,sum+1,health-1);
	}
	return ;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]==2)
			{
				sx=i;
				sy=j;
			}
			if(a[i][j]==3)
			{
				ex=i;
				ey=j;
			}
		}
	}
	dfs(sx,sy,0,6);
	if(ans==2e9+5)
	{
		cout<<-1;
	}
	else
	{
		cout<<ans;
	}
	return 0;
}
2024/4/11 21:44
加载中...