#P18726. Shortest Path

Shortest Path

Shortest Path

给定 n×m 的方格网格,每个格子是黑色或白色。你可以任选一个黑格放置棋子,然后进行游戏。每一轮,如果棋子所在格子没有相邻的黑格,游戏结束;否则,必须将棋子移动到一个相邻黑格,并把刚刚离开的格子涂白。相邻是指共享一条边。如果有多个相邻黑格,可以任选一个。

你希望尽早结束游戏。求最少访问多少个格子,并输出一条达到最少数量的实际路线。起点和终点都计入访问数量。

输入格式

第一行整数 t(1≤t≤1000)。每组先输入 n,m(2≤n,m≤100),随后 n 行,每行长度为 m,只含“.”(白格)和“X”(黑格)。每组至少有一个黑格。一个输入文件中所有测试的 n×m 之和不超过10000。

输出格式

每组先输出最少访问格数 k(1≤k≤n×m),然后输出 k 对整数 x_i,y_i,按访问顺序给出格子坐标,1≤x_i≤n,1≤y_i≤m。坐标均从1开始,行向下、列向右。存在多条最优路线时,任意输出一条。

每次离开的格子会变白,因此路线不能重复访问格子;末格必须已没有未访问的相邻原黑格。不能在仍可移动时提前停下。

完整原样例

4
2 2
X.
.X
3 3
.XX
XX.
XX.
2 3
XXX
XXX
4 6
...XXX
XXXX.X
X.XXXX
XXX...
1
2 2
2
1 2
1 3
4
2 1
2 2
1 2
1 1
8
2 4
3 4
3 5
3 6
2 6
1 6
1 5
1 4