영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Points | Limits |
|---|---|---|
| 1 | 20 | N=7 |
| 2 | 20 | N=11 |
| 3 | 60 | N=15 |
예제
예제 1
5 01000 00000 00100 00100 00001
3
예제 2
7 0000001 0001100 0101010 1111110 0101010 0011100 0000001
4