dfs深搜#8TLE求优化
查看原帖
dfs深搜#8TLE求优化
665213
iamecho9楼主2023/1/4 16:48
#include<iostream>

using namespace std;

int a[405][405];
int n, m, x, y;

void dfs(int i, int j, int num)//下一步坐标(i,j),当前步数num
{
	if (i < 1 || i > n || j < 1 || j > m)
		return;//越界return
	if (a[i][j] != 0 && a[i][j] <= num)
		return;//该点来过且步数更优return
	a[i][j] = num;
	dfs(i + 2, j + 1, num + 1);//右下
	dfs(i + 2, j - 1, num + 1);//右上
	dfs(i - 2, j + 1, num + 1);//左下
	dfs(i - 2, j - 1, num + 1);//左上
	dfs(i - 1, j + 2, num + 1);//下左
	dfs(i + 1, j + 2, num + 1);//下右
	dfs(i - 1, j - 2, num + 1);//上左
	dfs(i + 1, j - 2, num + 1);//上右
}

int main()
{
	cin >> n >> m >> x >> y;
	dfs(x + 2, y + 1, 1);//右下
	dfs(x + 2, y - 1, 1);//右上
	dfs(x - 2, y + 1, 1);//左下
	dfs(x - 2, y - 1, 1);//左上
	dfs(x - 1, y + 2, 1);//下左
	dfs(x + 1, y + 2, 1);//下右
	dfs(x - 1, y - 2, 1);//上左
	dfs(x + 1, y - 2, 1);//上右
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (i == x && j == y)
				cout << "0 ";
			else if (a[i][j] == 0)
				cout << "-1 ";
			else
				cout << a[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}
2023/1/4 16:48
加载中...