| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 330 | 133 | 116 | 48.945% |
빛이 태어난 뒤, 사람들은 그것을 단지 비추는 존재가 아닌, 삶의 공간에 스며드는 힘으로 받아들이고자 했다.
그들은 빛이 모든 이에게 닿을 수 있는 새로운 마을을 꿈꾸었다. 그 꿈을 이루기 위해, 빛이 구석구석 스며들 수 있는 땅을 조심스레 골랐다.
그들이 선택한 빛의 땅을 되짚고, 흩어진 조각들을 이어 다시 그려보아라.
고대의 섬에는 $N$행 $M$열 크기의 격자 형태를 가진 토지가 있었다. 이때 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 칸을 $(r,c)$로 표기한다.
빛은 단단하게 굳은 토양 위에서는 흘러가지 못했고, 대신 부드럽고 투명한 땅을 따라 조용히 스며들었다. 사람들은 마을을 세우기 위해, 빛이 닿는 땅과 집을 지을 수 있는 땅을 구분했다.
사람들은 빛이 마을 전체에 스며들 수 있도록, 토지에서 다음 조건을 만족하는 구역을 골라 마을을 짓기로 결정했다.
다음은 $K=1,2,3$일 때 마을을 지을 수 있는 $K\times K$ 크기의 구역의 예시이다. 검은 칸은 빛이 흐를 수 있는 칸을, 하얀 칸은 집을 지을 수 있는 칸을 나타낸다.
아래와 같은 예시에서, 왼쪽 그림에 표시된 구역은 마을을 지을 수 있는 4ドル\times 4$ 크기의 구역이다. 하지만 오른쪽 그림에 표시된 구역의 경우, 주대각선이 아닌 칸에 집을 모두 지을 수 없으므로, 마을을 지을 수 없다.
마을을 지을 수 있는 구역의 개수를 크기별로 알아내어라.
첫 줄에는 토지의 크기를 나타내는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다.
이후 $N$개의 줄에 걸쳐, 그중 $i$번째 줄에는 칸 $(i,1) ,(i,2) ,\cdots ,(i,M)$의 땅의 유형을 나타내는 $M$개의 문자 $A_{i1},A_{i2},\cdots ,A_{iM}$가 주어진다. $A_{ij}$가 ‘X’라면 빛이 흐를 수 있는 칸이고, ‘.’라면 집을 지을 수 있는 칸이다.
1ドル$부터 $\min(N,M)$까지의 모든 정수 $K$에 대해, 마을을 지을 수 있는 $K\times K$ 크기의 구역의 수를 순서대로 한 줄에 하나씩 출력한다.
‘X’ 또는 ‘.’이다. $(1\le i\le N,1\le j\le M)$| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $A_{ij} = \text{‘X'}$ $(1 \le i \le N, 1 \le j \le M)$ |
| 2 | 11 | $N = 2$ |
| 3 | 27 | $N \le 80, M \le 80$ |
| 4 | 25 | $N \le 400, M \le 400$ |
| 5 | 33 | 추가 제한 조건이 없다. |
4 4 X..X .X.. ..X. X..X
6 3 2 0
2 6 XXX..X .X.X..
6 1
4 5 XXXXX XXXXX XXXXX XXXXX
20 0 0 0
9 9 X.....X.. .X....X.. ..X...X.X ...X...X. X...X...X .X...X... ..XXXXX.. ...X...X. ....X...X
23 12 6 3 0 0 0 0 0
Contest > BOJ User Contest > BCF > BCF 2025 II번