dfs 90分 TLE #1
  • 板块P2802 回家
  • 楼主mengqifeng
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/1/15 21:04
  • 上次更新2025/1/16 10:12:09
查看原帖
dfs 90分 TLE #1
807584
mengqifeng楼主2025/1/15 21:04
#include <iostream>
using namespace std;
int pic[15][15];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
bool flag;
int n,m;
int fx,fy,sx,sy;
int minn=1e6;
int steps;
bool judge(int x,int y)
{
	if(x<=0||y<=0||x>n||y>m)return false;
	if(pic[x][y]==0)return false;
	return true;
}
void dfs(int x,int y,int lives)
{
	if(steps>=minn||lives==0||steps>=n*m)return;
	if(pic[x][y]==4)lives=6;
	if(x==sx&&y==sy)
	{
		minn=min(minn,steps);
		flag=1;
		return;
	}
	for(int i=0;i<4;i++)
	{
		int xx=x+dx[i],yy=y+dy[i];
		if(judge(xx,yy))
		{
			steps++;
			dfs(xx,yy,lives-1);
			steps--;
		}
	}
	return ;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>pic[i][j];
			if(pic[i][j]==2)fx=i,fy=j;
			else if(pic[i][j]==3)sx=i,sy=j;
		}
	}
	dfs(fx,fy,6);
	if(flag==false)cout<<-1;
	else cout<<minn;
	return 0;
}
2025/1/15 21:04
加载中...