题目描述

小波喜欢平面图, 尤其是哈密顿路。

现在有一个 $n \times m$ 的棋盘, 行从 $1$ 到 $n$ 编号, 列从 $1$ 到 $m$ 编号, 每个格子可能是空地或障碍。如果小波在格子 $(x, y)$ , 他可以一步走到 $(x+1, y),(x-1, y),(x, y+1),(x, y-1)$ 中的一个格子, 但是不能走出棋盘。小波初始在 $(1,1)$ , 而 $(n, 1),(1, m),(n, m)$ 三个点各有一张平面图, 小波希望到达这三个点以拿到这些平面图, 最后返回 $(1,1)$ , 保证这 四个点都不是障碍。但是因为小波喜欢哈密顿路，他希望到达每个格子不超过一次（不 必须到达每个格子; $(1,1)$ 在开始和最后到达共两次)。请你告诉他是否存在一种可行的 方案。由于小波非常喜欢平面图, 你需要处理 $T$ 个棋盘。

输入格式

第一行包含一个数 $T$, 表示棋盘个数。

对于每个棋盘, 第一行包含两个数 $n, m$, 表示棋盘大小。接下来 $n$ 行, 每行包含 一个长 $m$ 的由 $01$ 组成的字符串, 如果第 $i$ 行第 $j$ 个字符是 $0$, 表示格子 $(i, j)$ 是空地, 如果是 $1$ , 则是障碍。保证格子 $(1,1),(n, 1),(1, m),(n, m)$ 是空地。

输出格式

$T$ 行，每行包含一个数，表示每个棋盘的答案，$1$ 表示存在一种可行的方案，$0$ 表示不存在。

样例输入输出

5
3 3
000
010
000
5 5
00100
00000
10001
00000
00100
3 8
00100000
00000000
00000100
3 5
00100
00000
00100
4 4
0000
0000
0011
0010

1
0
1
0
0

样例 2

见附件下的 maze/maze2.in 与 maze/maze2.ans。

样例 3

见附件下的 maze/maze3.in 与 maze/maze3.ans。

说明/提示

【样例 #1 解释】

对于第一个棋盘，依次经过 $(1, 1),(1, 2),(1, 3),(2, 3),(3, 3),(3, 2),(3, 1),(2, 1),(1, 1)$ 是一个合法的方案。

【数据范围及约束】

用 $\sum{nm}$ 表示各棋盘的格子数总和。对于所有数据，保证 $2 \le n, m \le 1000, \sum{nm} ≤ 2 \times 10^6$。

【题目来源】

2023 青岛市程序设计竞赛 高中组 T2 maze