균형 잡힌 부분집합

농부 존의 목초지는 거대한 2차원 정사각형 "칸"들의 격자(거대한 체스판을 떠올리자)로 볼 수 있으며, 각 칸은 \(1\le i\le N\), \(1\le j\le N\) (\(1\le N\le 150\))에 대해 순서쌍 \((i,j)\)로 표시된다. 일부 칸에는 풀이 있다.

공집합이 아닌 격자 칸들의 부분집합이 다음 조건을 만족하면 "균형 잡힌" 부분집합이라고 부른다.

1. 부분집합의 모든 칸에 풀이 있다.
2. 부분집합은 4방향으로 연결되어 있다. 즉, 부분집합의 임의의 칸에서 다른 임의의 칸으로 가는 경로가 존재하며, 경로에서 연속한 두 칸은 가로 또는 세로로 인접해야 한다.
3. 칸 \((x_1,y)\)와 \((x_2,y)\) (\(x_1\le x_2\))가 부분집합에 속하면, \(x_1\le x\le x_2\)인 모든 칸 \((x,y)\)도 부분집합에 속한다.
4. 칸 \((x,y_1)\)과 \((x,y_2)\) (\(y_1\le y_2\))가 부분집합에 속하면, \(y_1\le y\le y_2\)인 모든 칸 \((x,y)\)도 부분집합에 속한다.

균형 잡힌 부분집합의 개수를 \(10^9+7\)로 나눈 나머지를 구하시오.

출제자: Benjamin Qi

채점 방식

• 테스트 케이스 1-4는 \(N\le 4\)를 만족한다.
• 테스트 케이스 5-10은 \(N\le 20\)을 만족한다.
• 테스트 케이스 11-20은 추가 제약이 없다.

출제자: Benjamin Qi

첫째 줄에 \(N\)이 주어진다.

다음 \(N\)개의 줄에 각각 \(N\)개의 문자로 이루어진 문자열이 주어진다. 위에서 \(i\)번째 줄의 \(j\)번째 문자는 칸 \((i,j)\)에 풀이 있으면 G, 그렇지 않으면 .이다.

균형 잡힌 부분집합의 개수를 \(10^9+7\)로 나눈 나머지를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > US Open > Platinum