RiseOJ – 반사

설명

농부 존은 $N \times N$ 격자 칸으로 표현되는 정사각형 캔버스를 가지고 있다( $2 \leq N \leq 2000$ , $$N$$ 은 짝수). 그는 다음 단계에 따라 캔버스에 그림을 그린다.

먼저 캔버스 중앙을 지나는 수평선과 수직선으로 캔버스를 네 개의 같은 사분면으로 나눈다.
다음으로 캔버스의 오른쪽 위 사분면에 멋진 그림을 그린다. 오른쪽 위 사분면의 각 칸은 칠해져 있거나('#'로 표현) 칠해져 있지 않다('.'로 표현).
마지막으로, 자신의 그림이 너무나 자랑스러운 나머지, 앞서 언급한 수평선과 수직선을 기준으로 그림을 나머지 사분면들로 반사시킨다.

예를 들어 $$N=8$$ 이고 농부 존이 2단계에서 오른쪽 위 사분면에 다음 그림을 그렸다고 하자.

.#..
.#..
.##.
....

그러면 3단계에서 수평선과 수직선을 기준으로 나머지 사분면들로 반사시킨 후, 캔버스는 다음과 같이 된다.

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

하지만 농부 존이 자는 동안 베시가 그의 헛간에 몰래 들어와 소중한 캔버스를 훔쳐 갔다. 베시는 캔버스를 완전히 훼손했다. 칠해진 칸을 지우기도 하고 새로 칠하기도 했다! 농부 존이 깨어나기 전에 베시는 캔버스를 농부 존에게 돌려놓았다.

농부 존은 캔버스가 다시 반사 조건을 만족하도록, 즉 오른쪽 위 사분면을 나머지 각 사분면으로 반사시킨 결과가 되도록 캔버스를 수정하고 싶다. 자원이 한정되어 있으므로 가능한 한 적은 횟수의 작업으로 이를 달성하고 싶다. 한 번의 작업은 한 칸을 칠하거나 한 칸의 칠을 지우는 것이다.

베시가 훼손한 후의 캔버스와, 캔버스에 대한 $$U$$ 개( $0\le U \leq 10^5$ )의 갱신 수열이 주어진다. 각 갱신은 한 칸이 '#'이면 '.'로, '.'이면 '#'로 토글한다. 갱신이 하나도 적용되기 전과 각 갱신 후마다, 반사 조건이 만족되도록 농부 존이 수행해야 하는 작업의 최소 횟수 $$x$$ 를 출력하시오.

Problem credits: Chongtian Ma

제약

배점

입력 2-3: $N \le 4$
입력 4-6: $U \le 10$
입력 7-16: 추가 제약이 없다.

Problem credits: Chongtian Ma

입력 형식

첫째 줄에 정수 $$N$$ 과 $$U$$ 가 주어진다.

다음 $$N$$ 개의 줄에 각각 베시가 훼손한 후의 캔버스를 나타내는 문자 $$N$$ 개가 주어진다. 모든 문자는 '#' 또는 '.'이다.

다음 $$U$$ 개의 줄에 각각 정수 $$r$$ 과 $$c$$ ( $1 \leq r, c \leq N$ )가 주어지며, 이는 캔버스의 위에서 $$r$$ 번째 행, 왼쪽에서 $$c$$ 번째 열에 있는 칸에 대한 갱신을 나타낸다.

출력 형식

갱신이 적용되기 전과 각 갱신 후의 $$x$$ 를 나타내는 $$U+1$$ 개의 줄을 출력한다.

예제 1

입력

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

출력

설명

The following canvas satisfies the reflective condition and differs from the
original canvas by 4 operations:

....
####
####
....

It is impossible to make the original canvas satisfy the reflective condition
using fewer than 4 operations.

After updating $$(1, 3)$$ , the canvas looks like this:

....
##.#
####
..##

It now takes 3 operations to make the canvas satisfy the reflective condition.

After updating $$(2, 3)$$ , the canvas looks like this:

....
####
####
..##

It now takes 2 operations to make the canvas satisfy the reflective condition.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > February > Bronze

올림피아드 > USACO > 2024-2025 > February > Bronze

태그

JudgeUSACO

반사

평가 및 의견

풀이 제출