80分,#9#10WA了,求助
查看原帖
80分,#9#10WA了,求助
542893
tiaotiao0830楼主2023/2/24 20:34
#include<iostream>
using namespace std;

int n,a,b,ans = 0x3f3f3f3f;
int lift[205],visited[205];

void dfs(int floor,int cnt)
{
	if(floor == b)
	{
		ans = min(ans,cnt);    //如果到达指定楼层就更新ans 
		return;
	}
	
	if(cnt > ans)
	{
		return;              //剪枝,如果次数已大于最小步数,直接排除 
	}
	
	visited[floor] = 1;      //标记为走过,不无限递归 
	
	if(floor - lift[floor] >= 1 && visited[floor - lift[floor]] != 1) //1
	{
		dfs(floor - lift[floor],cnt + 1);  //减去楼层 
	}
	if(floor + lift[floor] <= n && visited[floor + lift[floor] != 1]) //1
	{
		dfs(floor + lift[floor],cnt + 1);  //加上楼层 
	}
}

int main()
{
	cin >> n >> a >> b;
	for(int i = 1;i <= n;i++)
	{
		cin >> lift[i];
	}                         //输入 
	
	visited[a] = 1;          //标记第一个 
	dfs(a,0);                //DFS 
	
	if(ans == 0x3f3f3f3f)
	{
		cout << -1 << endl;	 //ans没变,表示不可能 
	}
	else
	{
		cout << ans << endl; //输出ans 
	}
	return 0;
}

//1:前半句判断是否越界,后半句判断是否访问过 
2023/2/24 20:34
加载中...