레이팅 미적용베시가 예술가가 되어 동굴 그림을 그리고 있다! 현재 작업 중인 작품은 높이 \(N\)의 격자로, 격자의 각 행은 정확히 \(M\)개의 칸으로 이루어져 있다(\(1\le N,M\le 1000\)). 각 칸은 비어 있거나, 바위로 채워져 있거나, 물로 채워져 있다. 베시는 그림의 테두리 전체를 포함하여 바위가 들어갈 칸들을 이미 칠해 두었다. 이제 베시는 이 그림이 실제라면 물의 순 이동이 없도록, 비어 있는 칸 일부를 물로 채우고 싶다. 위에서 \(i\)번째 행에 있는 칸의 높이를 \(N+1-i\)로 정의한다. 베시는 그림이 다음 제약 조건을 만족하기를 바란다.
칸 \(a\)가 물로 채워져 있다고 하자. 이때 \(a\)보다 높지 않은 빈 칸 또는 물 칸만을 사용하고 경로 위의 인접한 두 칸이 항상 변을 공유하는, \(a\)에서 칸 \(b\)로 가는 경로가 존재한다면, \(b\)도 물로 채워져 있어야 한다.
베시가 만들 수 있는 서로 다른 그림의 개수를 \(10^9+7\)로 나눈 나머지를 구하여라. 베시는 빈 칸을 원하는 개수만큼 물로 채울 수 있으며, 하나도 채우지 않거나 전부 채워도 된다.
문제 제공: Daniel Zhang
점수 배점
- 테스트 케이스 1-5는 \(N,M\le 10\)을 만족한다.
- 테스트 케이스 6-15는 추가 제약이 없다.
문제 제공: Daniel Zhang
첫째 줄에 공백으로 구분된 두 정수 \(N\)과 \(M\)이 주어진다.
다음 \(N\)개의 줄에는 각각 \(M\)개의 문자가 주어진다. 각 문자는 '.' 또는 '#'로, 각각 빈 칸과 바위로 채워진 칸을 나타낸다. 첫 행과 마지막 행, 그리고 첫 열과 마지막 열은 '#'만을 포함한다.
정수 하나를 출력한다. 제약 조건을 만족하는 그림의 개수를 \(10^9+7\)로 나눈 나머지이다.
cave.in · 출력을 쓸 파일 cave.out4 9
#########
#...#...#
#.#...#.#
#########9If a square in the second row is filled with water, then all empty squares must
be filled with water. Otherwise, assume that no such squares are filled with
water. Then Bessie can choose to fill any subset of the three horizontally
contiguous regions of empty squares in the third row. Thus, the number of
paintings is equal to \(1+2^3=9.\)
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > January > Platinum