[CSP-J 2024 T2] 地图探险

作者: qiqi 分类: CSP-J 发布时间: 2025-10-05 23:49

查看题目

第一种方法,模拟算法。

#include <bits/stdc++.h>
using namespace std;
#define N 1010
int T;
int n, m, k;
int x, y, d;

int fx[] = {0, 1, 0, -1};
int fy[] = {1, 0, -1, 0};

bool v[N][N];
char maze[N][N];
char tmp[N];
int adventure();

int main()
{
	cin >> T;
	while (T--)
	{
		cin >> n >> m >> k;
		cin >> x >> y >> d;
		for (int i = 1; i <= n; i++)
		{
			cin >> tmp;
			for (int j = 0; j <= m; j++)
				maze[i][j + 1] = tmp[j];
		}
		cout << adventure() << endl;
	}

	return 0;
}

int adventure()
{
	int cnt = 0;
	memset(v, false, sizeof(v));

	v[x][y] = true;
	while (k--)
	{

		int dx = x + fx[d];
		int dy = y + fy[d];

		if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && maze[dx][dy] == '.')
		{
			x = dx;
			y = dy;
		}
		else
			d = (d + 1) % 4;

		v[x][y] = true;
	}


	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (v[i][j])
				cnt++;

	return cnt;
}

这道题很容易想到深度优先搜索算法,但是地图太大用深搜只能获得部分分。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

标签云