求助只有案例三超时了,怎么优化
查看原帖
求助只有案例三超时了,怎么优化
1290618
youning楼主2024/3/11 18:22
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int s[N];
char b[N];
int x1, y1, x2, y2, T;
int sum = 0, mi = 100;
void dfs(int i, int j, int sum)
{
	if (i == x2 && j == y2) { mi = min(mi, sum); }
	for (int k = sum; k < T; k++)
	{
		if (b[k] == 'E')
		{
			s[k] = 1;
			sum++;
			dfs(i + 1, j, sum);
			sum--;
			s[k] = 0;
		}
		else if (b[k] == 'N')
		{
			s[k] = 1;
			sum++;
			dfs(i, j + 1, sum);
			sum--;
			s[k] = 0;
		}
		else if (b[k] == 'S')
		{
			s[k] = 1;
			sum++;
			dfs(i - 1, j, sum);
			sum--;
			s[k] = 0;
		}
		else if (b[k] == 'W')
		{
			s[k] = 1;
			sum++;
			dfs(i, j - 1, sum);
			sum--;
			s[k] = 0;
		}
	}
}
int main()
{
	cin.tie(0);
	cin >> x1 >> y1 >> x2 >> y2 >> T;
	memset(s, 0, sizeof s);
	for (int i = 0; i < T; i++)
	{
		cin >> b[i];
	}
	dfs(x1, y1, sum);
	if (mi != 100) { cout << mi; }
	else { cout << -1; }
	return 0;
}
2024/3/11 18:22
加载中...