空间探索求调

jhxs411 · 2025 年2 月 9 日 06:00

#include <iostream>
#include <climits>

struct st
{
	int x, y;
} const move[4] =
{
	{ 0, -1 },
	{ -1, 0 },
	{ 1, 0 },
	{ 0, 1 }
};

int search(int*** const all, int*** const answer, const int& x_size, const int& y_size, const int& limit, const st& start)
{
	if (limit <= 0)
	{
		return 0;
	}
	
	if (answer[start.x][start.y][limit] == -1) // 如果不曾访问过
	{
		int min_count = INT_MAX;

		for (int a = 0; a < 4; a++) // 遍历去往方向
		{
			int now_x = start.x + move[a].x, now_y = start.y + move[a].y; // 新的坐标

			if (now_x >= 0 && now_x < x_size && now_y >= 0 && now_y < y_size) // 如果可以访问
			{
				int count = search(all, answer, x_size, y_size, limit - 2, { now_x, now_y }); // 存储这个方向能遍历到的最小值

				min_count = count + 2 * all[start.x][start.y][a] < min_count ? count + 2 * all[start.x][start.y][a] : min_count; // 取最小值
			}
		}

		answer[start.x][start.y][limit] = min_count; // 更新记忆
	}

	return answer[start.x][start.y][limit]; // 返回
}

int main()
{
	int n, m, k;
	std::cin >> n >> m >> k;

	int*** all = new int** [n];
	int*** answer = new int** [n];
	for (int a = 0; a < n; a++)
	{
		all[a] = new int* [m];
		answer[a] = new int* [m];

		for (int b = 0; b < m; b++)
		{
			all[a][b] = new int[4] { -1, -1, -1, -1 };
			answer[a][b] = new int[k + 1];
			
			for (int c = 0; c <= k; c++)
			{
				answer[a][b][c] = -1;
			}
		}
	}

	for (int a = 0; a < n; a++)
	{
		for (int b = 0; b < m - 1; b++)
		{
			int value;
			std::cin >> value;

			all[a][b][2] = value;
			all[a][b + 1][1] = value;
		}
	}

	for (int b = 0; b < m; b++)
	{
		for (int a = 0; a < n - 1; a++)
		{
			int value;
			std::cin >> value;

			all[a][b][3] = value;
			all[a + 1][b][0] = value;
		}
	}

	for (int a = 0; a < n; a++)
	{
		for (int b = 0; b < m; b++)
		{
			if (k % 2 == 0)
			{
				std::cout << search(all, answer, n, m, k, { a, b }) << ' ';
			}
			else
			{
				std::cout << -1 << ' ';
			}
		}
		std::cout << std::endl;
	}
}

样例过不了

空间探索 求调

空间探索求调