典型的模拟法

题目分析

1. 地图与坐标：

   • 地图是 $n$ 行 $m$ 列。
   • 坐标 $(x, y)$ 表示第 $x$ 行第 $y$ 列。
   • 字符 x 是障碍，. 是空地。

2. 机器人状态：

   • 位置 $(x, y)$。
   • 朝向 $d$：$0$ (东), $1$ (南), $2$ (西), $3$ (北)。

3. 行动规则（每一步）：

   • 尝试移动：根据当前朝向 $d$ 计算下一步位置 $(x', y')$。
     • $d=0$ (东): $(x, y+1)$
     • $d=1$ (南): $(x+1, y)$
     • $d=2$ (西): $(x, y-1)$
     • $d=3$ (北): $(x-1, y)$
   • 判断合法性：
     • 如果在地图范围内（$1 \le x' \le n, 1 \le y' \le m$）且是空地（.）：
       • 移动：位置变为 $(x', y')$，朝向 $d$ 不变。
     • 否则（出界或遇到障碍）：
       • 右转：位置不变，朝向变为 $(d+1) \pmod 4$。

4. 目标：

   • 执行 $k$ 次操作后，统计经过的不同位置的数量（包括起点）。

解题思路

由于 $k \le 10^6$，直接模拟每一步操作的时间复杂度是 $O(k)$，完全可以在 1 秒内完成。我们需要一个数据结构来记录哪些位置已经被访问过，可以使用一个二维布尔数组 visited[n][m]。

步骤：

1. 读取 $T$ 组数据。
2. 对于每组数据：
   • 读取 $n, m, k$ 和初始状态 $x_0, y_0, d_0$。
   • 读取地图字符串。
   • 初始化 visited 数组，标记起点 visited[x0][y0] = true，计数器 ans = 1。
   • 循环 $k$ 次：
     • 计算下一步坐标 nx, ny。
     • 检查 nx, ny 是否合法（在界内且是 .）。
     • 如果合法：更新当前位置 x, y。如果该位置未访问过，标记并 ans++。
     • 如果不合法：更新朝向 d = (d + 1) % 4。
   • 输出 ans。

#include<iostream>
using namespace std;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };//方向数组
int n, m, k, x, y, d;
char mp[1005][1005];//输入的地图
bool vis[1005][1005];//判断经过了多少个格子
bool check(int x, int y, int d) {
	int nx = x + dx[d];
	int ny = y + dy[d];
	if (nx<1 || nx>n || ny<1 || ny>m || mp[nx][ny] == 'x') {
		return false;//如果超出地图或者下一个格子是障碍物，那么就不能走
	}
	return true;//否则就可以走
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m >> k;
		cin >> x >> y >> d;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> mp[i][j];
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				vis[i][j] = 0;//初始化
			}
		}
		vis[x][y] = 1;//标记起始位置
		for (int i = 1; i <= k; i++) {
			if (check(x, y, d)) {//判断下一个格子能不能走
				x = x + dx[d];//如果能走就走向下一个格子
				y = y + dy[d];
				vis[x][y] = 1;//标记下一个格子
			}
			else {
				d = (d + 1) % 4;//否则转向
			}
		}
		int cnt = 0;//统计经过的格子
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (vis[i][j] == 1) {
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}