题解思路

关键观察 如果某个敌方（'x'）连通块的“气”（上下左右相邻的空位 '.'）只有 1 个，那么把我方子（'o'）下在这唯一气上，立刻吃掉该连通块全部棋子。 因此问题化简为：

1. 扫描棋盘，按 4 联通把所有敌方连通块分组（BFS/DFS）。

2. 对每个敌方连通块统计：

   • 该块大小（棋子数）。

题目内容

小强最近在研究围棋，他希望有一个程序能告诉他一步之内，有哪些位置可以直接吃掉别人的棋子，吃几个。

围棋可以在围住别人的情况下，吃掉别人的棋子，详见样例。

标准围棋的棋盘是$19×19$的，但小强只是想研究围棋的规则，故假定棋盘大小为$n×n$。

围棋吃子的规则：

• 敌方的棋子里，上下左右直接相邻的棋子视为连通。
• 若我方落子后，对方有一个连通块中，所有棋子的上下左右四个格子都没有空格（即或为我方的棋子，或为边界，或为敌人的棋子时），该部分棋子被视为吃掉，详见样例。

输入描述

第一行输入一个整数 $n(5 ≤ n ≤ 1000)$，表示棋盘的大小是 $n×n$的。

随后 $n$ 行，每行 $n$ 个字符：

• '.'表示该位置没有棋子
• 'x'表示该位置是敌方棋子
• 'o'表示该位置是我方棋子

下一步只能在 '.'的位置落子。

数据保证初始局面不会有相互吃的情况，即初始局面合法

输出描述

若有 $k$个位置落子可以吃掉至少一个敌方棋子：

• 第一行输出一个整数 $k$。
• 随后 $k$行，每行输出 $a_i, b_i, c_i$，分别表示 横坐标、纵坐标和个数。

样例1

输入

6
.oo.o.
oxxox.
ox.xox
xoxoox
xoo...
.x..ox

输出

4
2 6 1
3 3 5
5 6 1
6 1 2 

说明

有 4 个位置可以吃掉对手的棋子：

• 置于 $(2,6)$ 可以吃掉棋子$(2,5)$。
• 置于 $(3,3)$ 可以吃掉棋子 $(2,2), (2,3), (3,2), (3,4), (4,3)$。
• 置于 $(5,6)$ 可以吃掉棋子$(6,6)$。
• 置于 $(6,1)$可以吃掉棋子 $(4,1)$ 和$(5,1)$。