AT_abc398_d [ABC398D] Bonfire 题解

## 题目大意
有一个无限大的二维网格，$(0,0)$ 处有一个篝火。 
在时间 $t = 0$ 时，烟雾只存在于坐标 $(0, 0)$ 处。

给定一个长度为 $N$ 的字符串 $S$，由字母 `N`, `W`, `S`, `E` 组成。在时间 $t = 1, 2, \dots, N$ 时，按顺序发生以下事件：

- 风开始吹动，当前时刻所有的烟雾按照如下规则移动：
    - 如果 $S_t$ 为 `N`，则所有位于坐标 $(r, c)$ 的烟雾会移动到坐标 $(r - 1, c)$。
    - 如果 $S_t$ 为 `W`，则所有位于坐标 $(r, c)$ 的烟雾会移动到坐标 $(r, c - 1)$。
    - 如果 $S_t$ 为 `S`，则所有位于坐标 $(r, c)$ 的烟雾会移动到坐标 $(r + 1, c)$。
    - 如果 $S_t$ 为 `E`，则所有位于坐标 $(r, c)$ 的烟雾会移动到坐标 $(r, c + 1)$。

- 如果在坐标 $(0, 0)$ 处没有烟雾，则在该位置生成新的烟雾。

Takahashi 站在坐标 $(R, C)$ 处。

对于每个 $1 \le t \le N$，确定在时刻 $t + 0.5$ 时，坐标 $(R, C)$ 处是否有烟雾，并按要求的格式输出答案。
## 解题思路
如果我们正着想不太好做，那我们倒着想。

我们考虑从 $(R, C)$ 是否走到 $(0, 0)$，可以就代表有烟雾。于是我们样例 $2$ 都过不了，因为这是烟雾整体移动，我们无法只维护一个点上的烟雾。

在这基础上，我们不难想到从 $(0, 0)$ 开始，每次朝反方向走，再把这个地方标记。每次判断 $(R + x, C + y)$ 是否被标记了即可。

CODE：
```cpp
#include <bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> m;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n, r, c;
	string s;
	cin >> n >> r >> c >> s;
	int x = 0, y = 0;
	m[{0, 0}] = 1;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'N')
			x++;
		if (s[i] == 'W')
			y++;
		if (s[i] == 'S')
			x--;
		if (s[i] == 'E')
			y--;
		m[{x, y}] = 1;
		if (m[{r + x, c + y}])
			cout << 1;
		else
			cout << 0;
	}
	return 0;
}
```

正在渲染内容...