/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君は天文部に所属しており、夜空の観測記録を整理しています。観測データは H 行 W 列のグリッド状の画像として記録されており、各マスには何も写っていないか、星が写っているかのどちらかです。
マスの位置は、左上のマスを (1, 1) として、上から i 行目・左から j 列目のマスを (i, j) で表します。観測データの i 行目は文字列 S_i で表され、S_i の j 文字目が T ならばマス (i, j) に星が写っており、. ならば何も写っていないことを意味します。
観測データが与えられるので、星が写っているマスの位置をすべて求めてください。星は行番号が小さい順に、行番号が同じ場合は列番号が小さい順に出力してください。
制約
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H, W は整数である
- S_i (1 \leq i \leq H) は
.とTのみからなる長さ W の文字列である Tが 1 つも含まれない（星が 0 個の）場合もありうる
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
- 1 行目には、観測データの行数 H と列数 W がスペース区切りで与えられる。
- 続く H 行のうち i 行目 (1 \leq i \leq H) には、観測データの i 行目の状態を表す長さ W の文字列 S_i が与えられる。
出力
以下の形式で出力せよ。
K r_1 c_1 r_2 c_2 \vdots r_K c_K
- 1 行目には、星の総数 K を出力する。
- 続く K 行には、星が写っているマスの位置を、行番号が小さい順に、行番号が同じ場合は列番号が小さい順に、1 行に 1 つずつ出力する。k 行目 (1 \leq k \leq K) には、k 番目の星の行番号 r_k と列番号 c_k をスペース区切りで出力する。
- K = 0 の場合は、1 行目に
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
Score : 233 pts
Problem Statement
Takahashi is a member of the astronomy club and is organizing his nighttime sky observation records. The observation data is recorded as a grid image with H rows and W columns, where each cell either contains nothing or contains a star.
Cell positions are represented as (i, j), where (1, 1) is the top-left cell, and (i, j) denotes the cell in the i-th row from the top and the j-th column from the left. The i-th row of the observation data is represented by the string S_i, where if the j-th character of S_i is T, it means a star is captured in cell (i, j), and if it is ., it means nothing is captured there.
Given the observation data, find the positions of all cells that contain stars. Output the stars in ascending order of row number, and for stars in the same row, in ascending order of column number.
Constraints
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H, W are integers
- S_i (1 \leq i \leq H) is a string of length W consisting only of
.andT - It is possible that no
Tis included (i.e., there are 0 stars)
Input
The input is given from standard input in the following format:
H W S_1 S_2 \vdots S_H
- The first line contains the number of rows H and the number of columns W of the observation data, separated by a space.
- In the following H lines, the i-th line (1 \leq i \leq H) contains a string S_i of length W representing the state of the i-th row of the observation data.
Output
Output in the following format:
K r_1 c_1 r_2 c_2 \vdots r_K c_K
- On the first line, output the total number of stars K.
- On the following K lines, output the positions of cells containing stars, one per line, in ascending order of row number, and for the same row number, in ascending order of column number. On the k-th line (1 \leq k \leq K), output the row number r_k and column number c_k of the k-th star, separated by a space.
- If K = 0, simply output
0on the first line (no subsequent lines are needed).
Sample Input 1
3 5 T..T. ..... ..T..
Sample Output 1
3 1 1 1 4 3 3
Sample Input 2
5 8 ........ .T....T. ........ .T..T... ....T..T
Sample Output 2
6 2 2 2 7 4 2 4 5 5 5 5 8
Sample Input 3
10 15 T.............T ...T........... .......T....... ............... .T............. ............... ..........T.... ............... .............T. T..T..T..T..T..
Sample Output 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