CSP 2024 入门级第二轮 CSP-J 2024 复赛 第二题 地图探险

一、题目阅读

[CSP-J 2024] 地图探险 - 洛谷

二、 题目分析

这题不能用DFS

用了超时。

其实用模拟就可以了。

void Solve() {
	visited[x][y] = true;
	for (int step = 1; step <= k; step++) {
		int nx, ny;
		nx = x + dir[d][0];
		ny = y + dir[d][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.') {
			x = nx;
			y = ny;
			visited[nx][ny] = true;
		} else {
			d = (d + 1) % 4;
		}
	}
}

由于他是一步走到底，无需反复尝试，所以递归是无意义的。

如以上代码：反复改变x, y，以模拟机器人的移动。

以下是几个注意点：

visited[x][y] = true;

走过的路可以再走。

d = (d + 1) % 4;

d要求余改变。

dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

顺序按题目来，不要自己糊弄。

memset(visited, false, sizeof (visited));

每组数据重新初始化。

三、题目代码

 

#include <bits/stdc++.h>
using namespace std;

int n, m, k, x, y, d;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; // 顺序按照题目来
char mp[1005][1005];
bool visited[1005][1005];

void Solve();


int main() {
	int T;
	cin >> T;
	while (T--) {
		memset(visited, false, sizeof (visited));
		cin >> n >> m >> k >> x >> y >> d;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> mp[i][j];
			}
		}
		Solve();
		int res = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (visited[i][j] == true) {
					res++;
				}
			}
		}
		cout << res << endl;
	}
	return 0;
}


void Solve() {
	visited[x][y] = true;
	for (int step = 1; step <= k; step++) {
		int nx, ny;
		nx = x + dir[d][0];
		ny = y + dir[d][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.') {
			x = nx;
			y = ny;
			visited[nx][ny] = true;
		} else {
			d = (d + 1) % 4;
		}
	}
}