CF1583C Omkar and Determination

问题描述如下，请你充满决心地阅读。 给定一个网格，其中有些格子为空，有些格子被填充。我们称一个格子为“可退出”的，如果从该格子出发，只通过空格子向上和向左移动，可以离开网格。这里包括该格子本身，因此所有被填充的格子都不是可退出的。注意，你可以从任意最左侧的空格子（即第一列的空格子）向左离开网格，也可以从任意最上方的空格子（即第一行的空格子）向上离开网格。 我们称一个网格为“可判定”的，如果仅给出每个格子是否可退出的信息，就能精确确定每个格子是被填充还是为空。 给定一个 $n \times m$ 的网格 $a$，即有 $n$ 行 $m$ 列。你需要回答 $q$ 个询问（$1 \leq q \leq 2 \times 10^5$）。每个询问给出两个整数 $x_1, x_2$（$1 \leq x_1 \leq x_2 \leq m$），询问由第 $x_1$ 列到第 $x_2$ 列组成的子网格是否为可判定的。

第一行包含两个整数 $n, m$（$1 \leq n, m \leq 10^6$，$nm \leq 10^6$），表示网格 $a$ 的行数和列数。 接下来 $n$ 行，每行包含 $m$ 个字符，第 $y$ 行第 $x$ 个字符为 'X' 表示该格子被填充，为 '.' 表示该格子为空。 接下来一行包含一个整数 $q$（$1 \leq q \leq 2 \times 10^5$），表示询问的数量。 接下来 $q$ 行，每行包含两个整数 $x_1$ 和 $x_2$（$1 \leq x_1 \leq x_2 \leq m$），表示一次询问，询问由第 $x_1$ 列到第 $x_2$ 列组成的子网格是否为可判定的。

对于每个询问，输出一行，内容为 "YES" 如果该子网格为可判定的，否则输出 "NO"。输出不区分大小写（如 "yEs" 和 "No" 也会被接受）。

对于样例的每个询问，对应的子网格如下所示：首先是输入格式，然后是每个格子标记为 "E"（可退出）或 "N"（不可退出）。 对于第一个询问： ```

..X EEN

... EEE

... EEE

... EEE


```

```





```

对于第二个询问：

```


X N

. E

. E

. E


```

```





```

对于第三个询问：

```


XX NN

X. NN

X. NN

X. NN


```

该子网格无法仅通过每个格子的可退出性来确定，因为如下网格也会产生相同的“可退出性网格”：

```


XX

XX

XX

XX


```

```





```

对于第四个询问：

```


X N

. E

. E

. E


```

```





```

对于第五个询问：

```


..XXX EENNN

...X. EEENN

...X. EEENN

...X. EEENN


```

该询问即为整个网格。它无法仅通过每个格子的可退出性来确定，因为如下网格也会产生相同的“可退出性网格”：

```


..XXX

...XX

...XX

...XX


```

由 ChatGPT 4.1 翻译