Computer vision: Erode or dilate a binary image

Erosion and dilation are the two building blocks of morphology.

What to build

A program that erodes or dilates a binary image with a 3 × 3 square.

Requirements

  • Erode: a pixel is # only if all nine pixels of its 3 × 3 neighbourhood are #. Dilate: a pixel is # if any of them is #.
  • Positions outside the image count as background.
  • Read from the original image only, and print the H result rows.

Input

Line 1: H, W and erode or dilate. Then H rows of # and ..

Output

H rows of # and ..

Constraints

1 ≤ H, W ≤ 60.

Example

Input:

3 3 dilate
...
.#.
...

Output:

###
###
###

Why it works

Erosion asks whether the whole square fits inside the shape, so shapes lose their outer layer; dilation asks whether the square touches the shape, so they gain one.

Examples

Example 1 · Input
3 3 dilate
...
.#.
...
Expected output
###
###
###
Example 2 · Input
5 5 erode
.....
.###.
.###.
.###.
.....
Expected output
.....
.....
..#..
.....
.....

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Write a helper that returns True only for positions inside the image that hold `#`; outside counts as background.

Hint 2

Erosion uses `all` over the nine neighbourhood positions, dilation uses `any`.

Solution

Show one correct solution (try it yourself first)
h, w, op = input().split()
h, w = int(h), int(w)
img = [input() for _ in range(h)]


def at(r, c):
    return 0 <= r < h and 0 <= c < w and img[r][c] == "#"


for r in range(h):
    line = ""
    for c in range(w):
        near = [at(r + i, c + j) for i in (-1, 0, 1) for j in (-1, 0, 1)]
        on = all(near) if op == "erode" else any(near)
        line += "#" if on else "."
    print(line)

Lesson: Morphology: erosion, dilation, opening and closing →