| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 165 | 42 | 36 | 33.333% |
섬을 지지하던 빛이 흔들리며, 섬의 만물을 이루는 네 개의 원소는 서로의 흐름을 방해하기 시작했다.
한때 완벽한 비율로 조화를 이루던 네 흐름은 이제 조금씩 어긋났고, 그 어긋남은 땅 곳곳에 흔적을 남겼다.
사람들은 균형을 되찾으려 했지만, 균형은 쉽게 깨졌고, 애써 복원된 구조마저 금세 흐트러지곤 했다.
원소의 균형을 위한 그들의 노력을 지켜보고, 그들이 마지막까지 지키려 했던 배열을 복원하여라.
섬 곳곳에는 흙, 물, 불, 공기의 네 가지 원소가 새겨진 격자가 존재한다.
이 격자는 $N\times M$ 크기로 이루어져 있으며, 각각의 칸에는 네 원소 중 하나가 배치되어 있다. 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 격자칸을 $(r,c)$로 표기한다.
네 가지 원소는 아래 표와 같이 온도와 습도 두 가지 속성으로 구분된다.
| 원소 | 온도 속성 | 습도 속성 |
|---|---|---|
| 흙 | 추움 | 마름 |
| 물 | 추움 | 젖음 |
| 불 | 더움 | 마름 |
| 공기 | 더움 | 젖음 |
격자 내부의 어떤 2ドル\times 2$ 크기의 사각형 안에 네 가지 원소가 모두 존재할 때, 원소들의 속성이 서로 균형을 이루게 된다. 이러한 사각형을 조화로운 사각형이라고 부른다. 예를 들어, 아래 원소의 격자에서 초록색으로 표시된 두 영역은 모두 조화로운 사각형이다.
그러나 최근, 섬의 사람들은 원소의 흐름이 불안정해졌음을 발견했다. 특정한 직사각형 영역에 대해, 해당 영역의 원소들이 온도 속성 또는 습도 속성이 반대인 원소로 변하는 현상이 $Q$회 발생하였다.
예를 들어, 아래 원소의 격자에서 가운데 3ドル\times 3$ 영역의 원소들이 온도 속성이 반대인 원소로 바뀌면 다음과 같이 변한다.
섬의 사람들은 격자에 변동이 일어날 때마다 조화로운 사각형의 수를 알고자 한다.
첫째 줄에 격자의 크기를 나타내는 정수 $N,ドル $M,ドル 그리고 격자가 변경되는 횟수 $Q$가 공백으로 구분되어 주어진다.
둘째 줄부터 $N$개의 줄에 걸쳐, 격자의 초기 상태가 주어진다. 각 줄에는 $M$개의 문자 $B_{i1},B_{i2},\cdots ,B_{iM}$이 주어진다. 각 문자는 E, W, F, A 중 하나이며, 이들은 각각 흙, 물, 불, 공기를 나타낸다.
이후 $Q$개의 줄에 걸쳐 격자의 변경에 대한 정보를 나타내는 정수 $t_i,r_{1i},c_{1i},r_{2i},c_{2i}$가 주어진다. $t_i$는 격자 변경의 종류를 나타내며, $t_i=1$인 경우 온도 속성의 변경, $t_i=2$인 경우 습도 속성의 변경을 의미한다. 나머지 네 정수는 원소의 변경이 $r_{1i}\le r\le r_{2i},ドル $c_{1i}\le c\le c_{2i}$인 모든 칸 $(r,c)$에서 일어난다는 의미이다.
첫째 줄에는 격자의 초기 상태에 존재하는 조화로운 사각형의 수를 출력한다.
이후 $Q$개의 줄에 걸쳐, 각 변경 후 격자에 존재하는 조화로운 사각형의 수를 차례로 출력한다.
E, W, F, A 중 하나이다. $(1\le i\le N,1\le j\le M)$| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $Q = 0$ |
| 2 | 7 | $N \le 100, M \le 100, Q \le 100$ |
| 3 | 31 | $r_{1i} = r_{2i}$ $(1 \le i \le Q)$ |
| 4 | 8 | $r_{1i} = c_{1i} = 1, r_{2i} = N, c_{2i} = M$ $(1 \le i \le Q)$ |
| 5 | 48 | 추가 제한 조건이 없다. |
5 5 2 EEAFW FWEWA WFEAF AFAWE EWEAF 1 2 2 4 4 2 2 1 4 5
5 2 2
4 6 0 EWEWFA FAFAEW WEEWFA FAWFFA
10
Contest > BOJ User Contest > BCF > BCF 2025 IX번