루미 알고리즘

#1588플래티넘Fake Snowflake

PO 2024 온라인 예선코딩출제 Olle Lapidus영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Alexander is a climate change denier and wants to prove to Joshua that the Earth is not getting warmer at all. Alexander argues that it has already snowed several times in November, which suggests that the temperature is dropping. Joshua, who mostly stays indoors, hasn't noticed any snow. Therefore, Alexander has been running around taking pictures of a lot of particles in the air, hoping to show photographic evidence to Joshua. Now, he has finally taken a picture he is quite satisfied with, but he needs to make some changes before showing the image.

Joshua, who loves fractals and unnecessarily complicated things, has specific ideas about how a snowflake should look. An image consists of N × N pixels, where N is an odd number, and each pixel is either white or black. The snowflake is made up of the white pixels in the image. According to Joshua, the image represents a snowflake if the following criteria are met:

  • The center pixel is white.
  • If you rotate the image clockwise 90 degrees, it looks the same.
  • If you mirror the image along the vertical centerline, it looks the same.
  • There are no 2 × 2 squares consisting entirely of white pixels.
  • The set of white pixels is contiguous without diagonal steps. This means that if you start with a pen on any white pixel, you can access every other white pixel without lifting the pen and without drawing on black pixels. The pen can go up, down, left and right, but not diagonally.
  • The set of black pixels is contiguous with diagonal steps. This means that if you start with a pen on any black pixel, you can access every other black pixel without lifting the pen and without drawing on white pixels. The pen can go up, down, left, right, and diagonally.
  • There are no hooks in the snowflake. Let pixel_up, pixel_right, pixel_down, and pixel_left be the adjacent pixels to a white pixel. A hook occurs if exactly two of these adjacent pixels are also white, and they are not on opposite sides of the pixel. For example, if pixel_up and pixel_right are white while pixel_down and pixel_left are black, a hook is formed, but if pixel_up and pixel_down are white and pixel_right and pixel_left are black, a hook is not formed.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: Two 3 × 3 images. The three pixels on the left form a hook, which is not allowed. The three pixels on the right do not form a hook.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 2: Three examples of 9 × 9 images depicting snowflakes.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 3: A very inaccurate snowflake. Of the three circled pixels, one white pixel is not contiguous with the rest of the white pixels, one pixel forms a hook, and one black pixel is not contiguous with the rest of the black pixels. Additionally, the image does not satisfy any of the two symmetry requirements.

Alexander has downloaded an image editing program where he can change the color of pixels, both from black to white and from white to black. Since he's not very skilled at image editing, Alexander expects it to take him one minute for each pixel he needs to change. Alexander is a very busy man and wants to be as time-efficient as possible. He now wants to know how quickly he can finish if he changes as few pixels as possible.

Input

The first line of the input contains the odd integer N (7 ≤ N ≤ 15), the number of pixels on each side of the square image. Then there are N lines of input, where the i-th line contains the N numbers p_{i,1}, p_{i,2}, ..., p_{i,N}. If the pixel at position (i, j) in the image is white, then p_{i, j} = 1, otherwise p_{i, j} = 0. Position (1,1) corresponds to the pixel in the upper left corner.

Output

Print an integer: the minimum number of minutes it takes for Alexander to make changes to his image for Joshua to agree that the image represents a snowflake.

Scoring

Your solution will be tested on a set of test case groups. To score points for a group, you must pass all the test cases in that group.

GroupPointsLimits
120N=7
220N=11
360N=15

예제

예제 1

입력
5
01000
00000
00100
00100
00001
출력
3

예제 2

입력
7
0000001
0001100
0101010
1111110
0101010
0011100
0000001
출력
4

출처 표기

출처: Programmeringsolympiaden 2024년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.