← 返回题目列表

Codeforces · 2090/B

B. 推球

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

Ecrade 有一个 $$$n \times m$$$ 网格,最初是空的,他在其中推了几个(可能是零个)球。

每次,他都可以从网格的特定行的最左边缘或特定列的最上边缘将一个球推入网格。

当球移向某个位置时:

  • 如果该位置原来没有球,来球将停止并占据该位置。
  • 如果该位置已经有球,则传入的球将停止并占据该位置,而原来的球将继续沿相同方向移动到下一个位置。

请注意,如果一行或一列已满(即该行或该列中的所有位置都有球),则他无法将球推入该行或该列。

给定网格每个位置是否有球的最终状态,您需要确定Ecrade是否有可能推动球到达最终状态。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 50$$$)。

接下来是 $$$n$$$ 行,每行恰好包含 $$$m$$$ 个字符,并且仅由 $$$0$$$ 和 $$$1$$$ 组成,描述网格的最终状态。当且仅当给定输入的对应位置为 $$$1$$$ 时,网格的一个位置上才有一个球。

保证所有测试用例的 $$$n\cdot m$$$ 总和不超过 $$$10\,000$$$。

输出

对于每个测试用例,如果 Ecrade 可以推动球达到最终状态,则输出“Yes”(不带引号),否则输出“No”(不带引号)。

在任何情况下都可以输出“Yes”和“No”(例如,字符串“YES”、“yEs”和“yes”将被识别为肯定响应)。

示例

输入
复制

5
3 3
001
001
110
3 3
010
111
010
3 3
111
111
111
3 3
000
000
000
3 3
000
000
001

输出
复制

YES
YES
YES
YES
NO

注意

为简单起见,如果 Ecrade 从第 $$$i$$$ 行的最左边缘推动一个球,我们将操作称为 $$$\text{ROW}\ i$$$;如果他从第 $$$i$$$ 列的最上边缘推出一个球,我们将操作称为 $$$\text{COL}\ i$$$。

为了直观理解,下面给出的矩阵中的非零数字$$$x$$$代表被推入的第$$$x$$$个球。

在第一个测试用例中,可能进行一系列操作:

$$$\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\xrightarrow{\text{ROW}\ 3}\xrightarrow{\text{ROW}\ 3} \begin{pmatrix}0&0&0\\0&0&0\\2&1&0\end{pmatrix}\xrightarrow{\text{COL}\ 3}\xrightarrow{\text{COL}\ 3} \begin{pmatrix}0&0&4\\0&0&3\\2&1&0\end{pmatrix}$$$

在第二个测试用例中,可能进行一系列操作:

$$$\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 2} \begin{pmatrix}0&0&0\\3&2&1\\0&0&0\end{pmatrix}\xrightarrow{\text{COL}\ 2}\xrightarrow{\text{COL}\ 2} \begin{pmatrix}0&5&0\\3&4&1\\0&2&0\end{pmatrix}$$$

在第三个测试用例中,可能进行一系列操作:

$$$\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\xrightarrow{\text{ROW}\ 1}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 3} \begin{pmatrix}1&0&0\\2&0&0\\3&0&0\end{pmatrix}\xrightarrow{\text{COL}\ 3}\xrightarrow{\text{COL}\ 3}\xrightarrow{\text{COL}\ 3} \begin{pmatrix}1&0&6\\2&0&5\\3&0&4\end{pmatrix}\xrightarrow{\text{ROW}\ 1}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 3} \begin{pmatrix}7&1&6\\8&2&5\\9&3&4\end{pmatrix}$$$