Under construction

Still being built. Things may change

Blur

Interview

Time limit2sMemory limit256 MB

Summary
Blur a binary image up to nine times with a wrapping 3 by 3 average and count how many distinct gray values remain.
Level

Easy3 of 10

Topics
Simulation, Matrix, Math
Solved
No attempts yet

Problem

You have a black and white image that is ww pixels wide and hh pixels high. Each pixel is written as a single number: black is 00 and white is 11. A friend asks you to blur the image, which produces various shades of gray.

The blur works like this. Build a new image of the same size, and set each pixel of the new image to the average of the 99 pixels in the 3×33 \times 3 square centered at the corresponding pixel of the old image. When you take that average, the edges wrap around. The left neighbor of a pixel in the leftmost column sits in the rightmost column of the same row, and the top neighbor of a pixel in the top row sits in the bottom row of the same column. The 3×33 \times 3 square therefore always gives you exactly 99 pixels. If you want the image blurrier, apply the same process again to the blurred image.

You are given the original image and the number of times to blur it. If all the arithmetic is performed exactly, how many distinct shades of gray does the final image have?

Warning: floating point numbers are finicky. If you represent fractions in floating point, 2/9+5/92/9 + 5/9 may not equal 3/9+4/93/9 + 4/9. Find a way to solve this without floating point arithmetic.

Input

The first line contains three space separated integers ww, hh, and bb (3≤w,h≤1003 \le w, h \le 100, 0≤b≤90 \le b \le 9), the width of the image, its height, and the number of times to blur it. Each of the following hh lines contains ww space separated integers describing the original image. Each integer is 00 or 11 according to the color of the pixel.

Output

Print, on a single line, the number of distinct shades of gray in the final image.

Examples8

  1. Example 1

    Input
    5 4 1
0 0 1 1 0
0 0 1 1 0
0 0 1 1 0
0 0 1 1 0
    Expected output
    3

  2. Example 2

    Input
    3 3 2
1 0 0
0 1 0
0 1 0
    Expected output
    1

  3. Example 3

    Input
    3 3 0
0 1 0
1 0 1
0 1 0
    Expected output
    2

  4. Example 4

    Input
    4 3 0
0 0 0 0
0 0 0 0
0 0 0 0
    Expected output
    1

  5. Example 5

    Input
    3 3 9
1 1 0
0 0 1
1 0 1
    Expected output
    1

  6. Example 6

    Input
    6 5 4
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
    Expected output
    1

  7. Example 7

    Input
    5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
    Expected output
    2

  8. Example 8

    Input
    4 4 3
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
    Expected output
    2