分数: 233 分
问题陈述
高桥是天文社的成员,正在整理他的夜空观测记录。观测数据记录为网格图像 H 行和 W 列,其中每个单元格要么不包含任何内容,要么包含一个星号。
单元格位置表示为 (i, j),其中 (1, 1) 是左上角的单元格,并且 (i, j) 表示单元格中 i从顶部开始的第行和 j左起第 列。的 i-第行观测数据由字符串表示 S_i,如果 j- 第一个字符 S_i is T,表示单元格中捕获了一颗星星 (i, j),如果是 .,这意味着那里没有捕获任何内容。
给定观测数据,找到所有包含星星的单元格的位置。按行号从小到大的顺序输出星星,对于同一行的星星,按列号从小到大的顺序输出。
约束
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H, W 是整数
- S_i (1 \leq i \leq H) 是一个长度为的字符串 W 仅包含
.和T - 可能没有
包括
T(即,有 0 星)
输入
输入由标准输入给出,格式如下:
H W S_1 S_2 \vdots S_H
- 第一行包含行数 H 和列数 观察数据的 W ,以空格分隔。
- 在下面 H 行, i第行 (1 \leq i \leq H) 包含一个字符串 S_i 长度 W 代表的状态 i-第行观察数据。
输出
按以下格式输出:
K r_1 c_1 r_2 c_2 \vdots r_K c_K
- 第一行,输出星星总数 K.
- 关于以下内容 K 行,输出包含星星的单元格的位置,每行一个,按行号升序排列,相同行号按列号升序排列。上 k第行 (1 \leq k \leq K),输出行号 r_k 和列号 c_k 的 k第一颗星,以空格分隔。
- If K = 0,简单地输出
0在第一行(不需要后续行)。
示例输入 1
3 5 T..T. ..... ..T..
示例输出 1
3 1 1 1 4 3 3
示例输入 2
5 8 ........ .T....T. ........ .T..T... ....T..T
示例输出 2
6 2 2 2 7 4 2 4 5 5 5 5 8
示例输入 3
10 15 T.............T ...T........... .......T....... ............... .T............. ............... ..........T.... ............... .............T. T..T..T..T..T..
示例输出 3
12 1 1 1 15 2 4 3 8 5 2 7 11 9 14 10 1 10 4 10 7 10 10 10 13