求助搜索TLE
  • 板块题目总版
  • 楼主KMSK
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/1/25 23:05
  • 上次更新2023/10/28 10:56:19
查看原帖
求助搜索TLE
472423
KMSK楼主2022/1/25 23:05

题目链接:回家
第一个点超时,是为什么啊
代码如下:(最后一个点是判重问题也WA了)

#include<iostream>
using namespace std;
int ans=2147483647;
int a[20][20];
int b[20][20];
int n,m;
int sx, sy;
int fx,fy;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int i,int j,int step,int blood)
{
	if(i==fx&&j==fy)
	{
		ans=min(ans,step);
		return;
	}
	if(blood==1)return;
	for(int k=0;k<4;k++)
	{
		int ii=i+dx[k];
		int jj=j+dy[k];
		if(ii<1||ii>n||jj<1||jj>m)continue;
		if(b[ii][jj]==0&&a[ii][jj]!=0)
		{
			if(a[ii][jj]==1||a[ii][jj]==3)
			{
				b[ii][jj]=1;
				dfs(ii,jj,step+1,blood-1);
				b[ii][jj]=0;
			}
			if(a[ii][jj]==4)
			{
				b[ii][jj]=1;
				dfs(ii,jj,step+1,6);
				b[ii][jj]=0;
			}
		}
	}
}
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)
			{
				fx=i;
				fy=j;
			}
		}
	}
	b[sx][sy]=1;
	dfs(sx,sy,0,6);
	if(ans!=2147483647)cout<<ans<<endl;
	else cout<<-1<<endl;
	return 0;
}  

第一个点的测试数据:
9 9
2 0 1 4 1 1 4 1 1
1 0 4 1 1 4 1 1 1
1 4 1 1 4 1 1 1 4
4 1 1 4 1 4 1 4 1
1 1 4 1 1 1 4 1 1
1 4 1 1 1 4 1 1 1
4 1 4 1 4 1 1 1 1
1 1 1 4 1 1 1 1 1
1 1 4 1 1 1 1 1 3

2022/1/25 23:05
加载中...