Vision Program

문제

You are implementing a vision program for a robot. Each time the robot camera takes a picture, it is stored as a black and white image in the robot's memory. Each image is an $H\times WH\; \backslash times\; W$ grid of pixels, with rows numbered $00$ through $H-1H-1$ and columns numbered $00$ through $W-1W-1$. There are exactly two black pixels in each image, and all other pixels are white.

The robot can process each image with a program consisting of simple instructions. You are given the values of $HH$, $WW$, and a positive integer $KK$. Your goal is to write a procedure to produce a program for the robot that, for any image, determines whether the distance between the two black pixels is exactly $KK$. Here, the distance between a pixel in row $r_{1}r\_1$ and column $c_{1}c\_1$ and a pixel in row $r_{2}r\_2$ and column $c_{2}c\_2$ is $\mathrm{\mid }{r}_1-r_2\mathrm{\mid }+\mathrm{\mid }{c}_1-c_2\mathrm{\mid }|r\_1-r\_2|+|c\_1-c\_2|$. In this formula $\mathrm{\mid }x\mathrm{\mid }|x|$ denotes the absolute value of $xx$, which equals $xx$ if $x\ge 0x\; \backslash geq\; 0$ and equals $-x-x$ if $x<0x\; \backslash lt\; 0$.

We now describe how the robot works.

The robot's memory is a sufficiently large array of cells, indexed from $00$. Each cell can store either $00$ or $11$ and its value, once set, will not be changed. The image is stored row by row in cells indexed $00$ through $H\cdot W-1H\; \backslash cdot\; W\; -\; 1$. The first row is stored in cells $00$ through $W-1W-1$, and the last row is stored in cells $(H-1)\cdot W(H\; -\; 1)\; \backslash cdot\; W$ through $H\cdot W-1H\; \backslash cdot\; W\; -\; 1$. In particular, if the pixel in row $ii$ and column $jj$ is black, the value of cell $i\cdot W+ji\backslash cdot\; W\; +\; j$ is $11$, otherwise it is $00$.

A robot's program is a sequence of instructions, which are numbered with consecutive integers starting from $00$. When the program is run, the instructions are executed one by one. Each instruction reads the values of one or more cells (we call these values the instruction's inputs) and produces a single value equal to $00$ or $11$ (we call this value the instruction's output). The output of instruction $ii$ is stored in cell $H\cdot W+iH\backslash cdot\; W\; +\; i$. The inputs of instruction $ii$ can only be cells that store either pixels or outputs of previous instructions, i.e. cells $00$ to $H\cdot W+i-1H\; \backslash cdot\; W\; +\; i\; -\; 1$.

There are four types of instructions:

• NOT: has exactly one input. Its output is $11$ if the input is $00$, otherwise its output is $00$.
• AND: has one or more inputs. Its output is $11$ if and only if all of the inputs are $11$.
• OR: has one or more inputs. Its output is $11$ if and only if at least one of the inputs is $11$.
• XOR: has one or more inputs. Its output is $11$ if and only if an odd number of the inputs are $11$.

The output of the last instruction of the program should be $11$ if the distance between the two black pixels is exactly $KK$, and $00$ otherwise.