← 返回题目列表

AtCoder · abc398_d

G. 篝火

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

有一个无限大的二维网格,坐标处有篝火 (0,0).
时间 t=0,烟雾仅存在于细胞中 (0,0).

给你一个长度-N 字符串 S 组成 N, W, S, E。有时 t=1,2,\dots,N,以下顺序发生:

  • 风吹过,当时存在的所有烟雾移动如下:
    • 如果 t- 第一个字符 S is N,牢房内冒烟 (r,c) 移至单元格 (r-1,c).
    • 如果是 W,牢房内冒烟 (r,c) 移至单元格 (r,c-1).
    • 如果是 S,牢房内冒烟 (r,c) 移至单元格 (r+1,c).
    • 如果是 E,牢房内冒烟 (r,c) 移至单元格 (r,c+1).
  • 如果牢房内没有烟雾 (0,0),电池处产生新的烟雾 (0,0).

高桥正站在牢房前 (R,C).
对于每个整数 1 \le t \le N,判断细胞内是否存在烟雾 (R,C) 时间 t+0.5,并按照要求的格式打印响应。

约束

  • N 是介于 1 和 200000,包括在内。
  • S 是长度 N 字符串组成 N, W, S, E.
  • R 和 C 是介于 -N 和 N,包括在内。
  • (R,C) \neq (0,0)

输入

输入由标准输入按以下格式给出:

N R C
S

输出

打印 N- 字符串组成 0 和 1.
的 树的 t- 第一个字符 (1 \le t \le N)应该是:

  • 1 如果牢房内存在烟雾 (R,C) 时间 t+0.5,和
  • 0 否则。

示例输入 1

6 -2 1
NNEEWS

示例输出 1

001010

有时 1.5,2.5,4.5,6.5,牢房内没有烟雾 (-2,1)。有时 3.5,5.5,牢房冒烟 (-2,1).
因此,输出 001010.

在下图中,取单元格 (0,0) 以篝火为参考,细胞 绘制 (r,c) :

  • -r 单元格向上,如果 r < 0,
  • r 单元格向下,如果 r \ge 0,
  • -c 剩余单元格如果 c < 0,
  • c 单元格正确,如果 c \ge 0.

时间格 0.5 看起来像:

时间格 1.5 看起来像:

时间格 2.5 看起来像:

时间格 3.5 看起来像:

时间格 4.5 看起来像:

时间格 5.5 看起来像:

时间格 6.5 看起来像:


示例输入 2

10 1 2
NEESESWEES

示例输出 2

0001101011

示例输入 3

20 -1 -2
WWNNWSWEWNSWWENSNWWN

示例输出 3

00100111111000101111