90分,总是超时,求助!想减少重复步骤,不知道咋办。
查看原帖
90分,总是超时,求助!想减少重复步骤,不知道咋办。
830669
TrappedGhost楼主2022/11/15 17:50

不知道怎么优化,想减少重复步骤,无从下手。。。


#include<iostream>
using namespace std;
#include<cmath>

int a1, b1;

int n;

int arr1[20000];

int arr[1000][1000] = { -1 };

int m;

void work02(int a, int b) {

	if (a >= 3 && b >= 2) {

		if (arr[a - 2][b - 1] == -1 || arr[a - 2][b - 1] > arr[a][b] + 1) {
			arr[a - 2][b - 1] = arr[a][b] + 1;
			if (a - 2 != a1 || b - 1 != b1) {
				work02(a - 2, b - 1);
			}
		}
	}

	if (a >= 2 && b >= 3) {
		if (arr[a - 1][b - 2] == -1 || arr[a - 1][b - 2] > arr[a][b] + 1) {
			arr[a - 1][b - 2] = arr[a][b] + 1;
			if (a - 1 != a1 || b - 2 != b1) {
				work02(a - 1, b - 2);
			}
		}

	}
	if (a >= 3 && b <= m - 1 ) {
		if (arr[a - 2][b + 1] == -1 || arr[a - 2][b + 1] > arr[a][b] + 1) {
			arr[a - 2][b + 1] = arr[a][b] + 1;
			if (a - 2 != a1 || b + 1 != b1) {
				work02(a - 2, b + 1);
			}
		}
	}
	if (a <= n - 2 && b >= 2) {
		if (arr[a + 2][b - 1] == -1 || arr[a + 2][b - 1] > arr[a][b] + 1) {
			arr[a + 2][b - 1] = arr[a][b] + 1;
			if (a + 2 != a1 || b - 1 != b1) {
				work02(a + 2, b - 1);
			}
		}

	}
	if (a <= n - 1 && b >= 3) {
		if (arr[a + 1][b - 2] == -1 || arr[a + 1][b - 2] > arr[a][b] + 1) {
			arr[a + 1][b - 2] = arr[a][b] + 1;
			if (a + 1 != a1 || b -2 != b1) {
				work02(a + 1, b - 2);
			}
		}
	}
	if (a >= 2 && b <= m - 2 ) {
		if (arr[a - 1][b + 2] == -1 || arr[a - 1][b + 2] > arr[a][b] + 1) {
			arr[a - 1][b + 2] = arr[a][b] + 1;
			if (a - 1 != a1 || b + 2 != b1) {
				work02(a - 1, b + 2);
			}
		}

	}
	if (a <= n - 1 && b <= m - 2 ) {
		if (arr[a + 1][b + 2] == -1 || arr[a + 1][b + 2] > arr[a][b] + 1)
		{
			arr[a + 1][b + 2] = arr[a][b] + 1;
			if (a + 1 != a1 || b + 2 != b1) {
				work02(a + 1, b + 2);
			}
		}
	}
	if (a <= n - 2 && b <= m - 1 ) {
		if (arr[a + 2][b + 1] == -1 || arr[a + 2][b + 1] > arr[a][b] + 1) {
			arr[a + 2][b + 1] = arr[a][b] + 1;
			if (a + 2 != a1 || b + 1 != b1) {
				work02(a + 2, b + 1);
			}
		}
	}
}

int main()
{

	cin >> m >> n;

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			arr[j][i] = -1;
		}
	}
	cin >> b1 >> a1;

	arr[a1][b1] = 0;

	work02(a1, b1);


	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cout << arr[j][i] << "    ";
		}
		cout << endl;
	}
	return 0;
}
2022/11/15 17:50
加载中...