小红的dfs
题号:NC289692
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}有一个 nm 列的网格,我们使用 (i,j) 表示网格中从上往下数第 i 行和从左往右数第 j 列的单元格。每个方格要么是可以通过的空方格 \texttt{`.'} ,要么是不可通过的墙方格 \texttt{`*'},特别的,网格的四周都是墙方格,小红可以沿着空方格上下左右随意移动:从 (x,y) 向上移动一格即抵达 (x-1,y)、向下移动一格即抵达 (x+1,y)、向左移动一格即抵达 (x,y-1)、向右移动一格即抵达 (x,y+1)

\hspace{15pt}现在小紫希望给小红的移动增加一些难度,她准备往某些位置放置一些地雷,小红无法踏入有地雷的位置。现在你需要在特定地图状态时刻回答小红能否从某个位置移动到另一个位置。
\hspace{15pt}形式化的,输入的操作分为两类:
\hspace{23pt}\bullet\,操作一:给出 (x,y),代表小紫在第 x 行第 y 列的位置上放置了一颗地雷(保证该点不是墙方格,如果一个空方格放置多颗地雷,效果等效于一颗地雷)。
\hspace{23pt}\bullet\,操作二:给出 (x_1,y_1)(x_2,y_2),代表询问此时小红能否从第 x_1 行第 y_1 列出发,抵达第 x_2 行第 y_2 列;特别地,若起点终点为墙方格、为地雷,那么均视为无法到达目的地。
\hspace{15pt}对于每个操作二,如果小红可以抵达,请输出 \rm{Yes},否则输出 \rm{No}

输入描述:

\hspace{15pt}第一行输入三个正整数 n,m,q \left(1 \leq n,m \leq 500;\ 1 \leq q \leq 10^5\right) 代表地图的行数、列数、操作的次数。 
\hspace{15pt}此后 n 行,每行输入一个长度为 m,仅由 \texttt{`.'}\texttt{`*'} 两种字符组成的字符串。
\hspace{15pt}此后 q 行,每行输入先输入一个整数 op \left(1 \leq op \leq 2\right),代表操作类型。随后:
\hspace{23pt}\bullet\,op=1,在同一行输出两个整数 x,y \left(1 \leq x \leq n;\ 1 \leq y \leq m\right) 代表操作一。保证 (x,y) 为空方格。
\hspace{23pt}\bullet\,op=2,在同一行输出四个整数 x_1,y_1,x_2,y_2 \left(1 \leq x_1,x_2 \leq n;\ 1 \leq y_1,y_2 \leq m\right) 代表操作二。

\hspace{15pt}除此之外,保证至少存在一次询问。

输出描述:

\hspace{15pt}对于每个操作二,新起一行。如果小红可以从起点出发抵达终点,输出 \rm{Yes},否则输出 \rm{No}
示例1

输入

复制
3 3 5
...
.*.
...
1 1 3
2 1 1 3 3
2 1 3 3 3
1 3 1
2 1 1 3 3

输出

复制
Yes
No
No

说明

\hspace{15pt}对于第一次询问,网格如公式所示:\begin{bmatrix}<br />\texttt{.} & \texttt{.} & \texttt{*} \\<br />\texttt{.} & \texttt{*} & \texttt{.} \\<br />\texttt{.} & \texttt{.} & \texttt{.}<br />\end{bmatrix}
\hspace{15pt}一个合法的移动方案是:(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)

\hspace{15pt}对于第二次询问,由于小红的起点有地雷,因此无法到达。

\hspace{15pt}对于第三次询问,网格如公式所示:\begin{bmatrix}<br />\texttt{.} & \texttt{.} & \texttt{*} \\<br />\texttt{.} & \texttt{*} & \texttt{.} \\<br />\texttt{*} & \texttt{.} & \texttt{.}<br />\end{bmatrix}
\hspace{15pt}我们可以证明,小红无法从 (1,1) 移动到 (3,3)