← 返回题目列表

AtCoder · awc0063_a

A. 星空观测日志

中文机器翻译题面 查看原题

分数: 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