求助大佬,80分WA,第8第9个数据查不出来原因,用的dfs
查看原帖
求助大佬,80分WA,第8第9个数据查不出来原因,用的dfs
557406
rrrachel楼主2021/11/23 21:18
#include<bits/stdc++.h>
using namespace std;

int K[210] = { 0 };
int A;
int B;
int N;

int f[210];
bool visit[210] = { 0 };

int dfs(int cur_floor, int end_floor)
{
	//判断到不了
	//剪枝
	if (f[cur_floor] != -1)
		return f[cur_floor];

	//标记为来过
	visit[cur_floor] = 1;
	//结束标志
	if (cur_floor == end_floor)
		return 0;
	int n1 = -1;
	int n2 = -1;
	int temp;

	if (cur_floor - K[cur_floor] < 1)
		n1 = INT_MAX;
	else if (!visit[cur_floor - K[cur_floor]])
		n1 = dfs(cur_floor - K[cur_floor], end_floor);
	else
		n1 = f[cur_floor - K[cur_floor]];
	
	if (cur_floor + K[cur_floor] > N)
		n2 = INT_MAX;
	else if ((!visit[cur_floor + K[cur_floor]]))
			n2 = dfs(cur_floor + K[cur_floor], end_floor);
	else
		n2 = f[cur_floor + K[cur_floor]];
	
	if ((n1 == -1 && n2 == -1) || (n1 == -1 && n2 == INT_MAX) || (n2 == -1 && n1 == INT_MAX)||(n1==INT_MAX&&n2==INT_MAX))
		temp = -1;
	else if (n1 == -1)
		temp = n2 + 1;
	else if (n2 == -1)
		temp = n1 + 1;
	else
		temp = min(n1, n2) + 1;
	f[cur_floor] = temp;
	return temp;
}

int main()
{
	for (int i = 0; i < 110; i++)
		f[i] = -1;
	cin >> N >> A >> B;
	for (int i = 1; i <= N; i++)
		cin >> K[i];
	cout << dfs(A, B);
}
2021/11/23 21:18
加载中...