레이팅 미적용설명
고고학자들이 최근 그리스·로마 건축의 유적을 발견했다. 발굴지는 \(R \cdot C\)개의 정사각형 칸으로 이루어진 격자로 모델링할 수 있다. 각 칸에 대해 고고학자들은 그곳에 건물이 있었는지, 아니면 항상 비어 있었는지를 알아냈다.
유물을 자세히 조사한 결과, 이 장소에는 서로 다른 시대의 건물 두 채가 있으며, 두 건물의 평면도가 모두 정사각형 모양이라는 결론을 내렸다.
두 건물은 서로 다른 시대의 것이므로 평면도가 겹칠 수도 있다.
각 건물의 가능한 위치와 크기(평면도가 차지하는 정사각형의 한 변의 길이)를 구하시오.
제약
입력 형식
첫째 줄에 발굴지의 크기인 두 정수 \(R\) (\(1 \le R \le 100\))와 \(C\) (\(1 \le C \le 100\))가 주어진다.
다음 \(R\)개의 줄에는 문자 .(마침표) 또는 x(소문자)로 이루어진 길이 \(C\)의 문자열이 주어진다. 문자 .은 그 칸에서 아무것도 발견되지 않았다는 뜻이고, x는 그곳에 건물이 있었다는 뜻이다.
출력 형식
두 건물 각각에 대해, 왼쪽 위 모서리의 행과 열, 그리고 건물의 크기를 한 줄에 출력한다.
참고: 테스트 데이터는 해가 항상 존재함을 보장한다. 단, 해가 유일하지 않을 수도 있다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 70점 |
예제 1
입력
3 3
xx.
xxx
...출력
1 1 2
2 3 1예제 2
입력
4 6
xx....
xx.xxx
...xxx
...xxx출력
1 1 2
2 4 3예제 3
입력
5 5
.....
xxx..
xxxx.
xxxx.
.xxx.출력
2 1 3
3 2 3문제 정보
태그