题目背景

题目传送门 U511007 地刺大战僵尸

由于王某栋在课堂上说自己得了NOI金牌，赵老尸非常愤怒，于是决定从教室门发起肘击，肘飞所有课桌，然后拿走王之栋的金牌。王之栋不想失去自己的金牌，于是决定发起金牌保卫战。

题目描述

王某栋的教室是一个 $n$ 行 $m$ 列的网格图，初始时上面种植有了一些学生用来抵挡赵老尸的肘击，王某栋开了外挂，赵老尸踩上会直接WA。

赵老尸会从王某栋的教室的右侧肘击：赵老尸可以选择第 $m$ 列的任意一个格子出发，它们可以移动到和当前格子有公共边的相邻课桌上去。它们想找到一条没有学生的路径到达教室的最左侧，即只要它们到达了第 $1$ 列，王某栋的NOI金牌就会被赵老尸给吃掉。

王某栋可以在网格图上补充学生。但是，种植学生的格子之间不能有公共边（不能相邻），现在王某栋想知道他最少种多少个学生才能抵挡住赵老尸的肘击，如果王某栋找不到种植学生的方法，输出 $-1$。

输入格式

第一行一个整数 $T$ 表示输入数据的组数。

接下来 $T$ 组数据，每组数据的第一行两个整数 $n,m$ 表示王之栋教室的行数和列数。

接下来 $n$ 行，每行一个长为 $m$ 的字符串，用来表示这一行的学生种植情况，其中 "." 表示这里是空地，"#" 表示这里种植了一个学生。

输出格式

输出 $T$ 行，每行一个整数，表示在该组输入下如果王某栋不能保住他的NOI金牌（失败），输出 $-1$，否则输出王某栋最少需要种植的学生数量，使得种植完这些学生之后，赵老尸们找不到一条从最右侧到最左侧的路径。

3
3 3
..#
.#.
#..
3 4
...#
#...
..#.
3 5
...#.
..#..
#....

0
-1
1

3
4 2
..
.#
#.
..
3 3
..#
#..
..#
5 5
.....
.....
.....
.....
.....

2
-1
5

说明/提示

【数据范围】

• 对于 $100\%$ 的数据，$1 \le T \le 10,1 \le n,m \le 1000$，初始的教室中不会有学生在相邻格子上，字符仅包含 . 和 # 两种字符

【cinbarhuchの威胁】

• 你小子做好不要让我知道你过不了第10个点

欲知后事如何，请看 STJX0002 王之栋的魔法

本题洛谷同步上传。U578817 赵老尸大战王之栋