Robot Visual Program for Pixel Distance

You are writing a visual program for a robot. Every time the camera takes a snapshot, the image is stored as a black and white picture represented by an H × W grid of pixels. The rows are numbered from \(0\) to \(H-1\) and the columns from \(0\) to \(W-1\). Each image contains exactly two black pixels, with all other pixels white.

The robot can process the image via a sequence of simple instructions. You are given integers \(H\), \(W\), and a positive integer \(K\). Your goal is to design a function that constructs a program for the robot. This program must determine whether the Manhattan distance between the two black pixels is exactly \(K\). The Manhattan distance between a pixel at row \(r_1\) and column \(c_1\) and a pixel at row \(r_2\) and column \(c_2\) is defined as:

[ |r_1 - r_2| + |c_1 - c_2| ]

where \(|x|\) denotes the absolute value of \(x\): it is \(x\) if \(x \ge 0\), and \(-x\) if \(x .

The image is stored in the robot's memory as follows: the image pixels are stored in consecutive memory cells, starting from cell \(0\) up to cell \(H \times W - 1\) in row-major order. In particular, if the pixel in row \(i\) and column \(j\) is black, then memory cell number \(i \cdot W + j\) holds a value of \(1\); otherwise it holds a value of \(0\).

The robot program is a sequence of instructions, each assigned a consecutive number starting from \(0\). When an instruction is executed, it reads one or more memory cells (called its inputs) and produces a single output value of \(0\) or \(1\). The output of instruction \(i\) is stored in memory cell number \(H \times W + i\). An instruction \(i\) may only use as inputs the memory cells that store the original image or the outputs of previous instructions (cells \(0\) to \(H \times W + i - 1\)).

The robot supports four types of instructions:

• NOT: Takes a single input. It outputs \(1\) if the input is \(0\) and \(0\) otherwise.
• AND: Takes one or more inputs. It outputs \(1\) if and only if all of its inputs are \(1\).
• OR: Takes one or more inputs. It outputs \(1\) if at least one of its inputs is \(1\).
• XOR: Takes one or more inputs. It outputs \(1\) if and only if an odd number of its inputs are \(1\).

If the Manhattan distance between the two black pixels is exactly \(K\), then the output of the last instruction in the program should be \(1\); otherwise, it should be \(0\>.

Implementation Details

You need to implement the following function:

void construct_network(int H, int W, int K)

Parameters:

• H, W: the dimensions of the image captured by the robot's camera
• K: a positive integer

This function must generate a robot program that, for any image captured by the robot, determines if the Manhattan distance between the two black pixels is exactly \(K\) by appending instructions using the following functions:

int add_not(int N)
int add_and(int[] Ns)
int add_or(int[] Ns)
int add_xor(int[] Ns)

Each call appends one instruction to the robot's program. The returned integer is the memory cell index where the output of that instruction is stored. The memory cells for the image are numbered from \(0\) to \(H \times W - 1\), and the outputs of the instructions are stored in subsequent cells.

The robot's program must not exceed \(10^4\) instructions, and the total number of inputs used by all instructions should not exceed \(10^6\). Violating these limitations will result in errors such as:

• Instruction with no inputs
• Invalid index
• Too many instructions
• Too many inputs

Interaction with the Testing Program

The testing program will first read the following input format:

• Line 1: Three integers, H, W, and K.
• Each subsequent line (starting from line 2) contains four integers: r1, c1, r2, c2, representing one image with two black pixels located at \( (r1, c1) \) and \( (r2, c2) \).
• The input is terminated by a line containing -1.

After building the program by calling construct_network, the testing program will simulate the robot running the program on each image, and the output of the last instruction (either \(0\) or \(1\)) is printed on a separate line for each image. In addition, a log file log.txt will be generated containing the memory state after the program execution.

Note: For this problem, you simply need to produce a solution that reads the input, computes whether the Manhattan distance between the two black pixels is exactly \(K\), and outputs \(1\) if true and \(0\) otherwise.

inputFormat

The input consists of multiple lines:

• The first line contains three integers H, W, and K.
• Each subsequent line (except the last) contains four integers: r1, c1, r2, c2, which denote the positions of the two black pixels in an image.
• The last line contains a single integer -1, indicating the end of input.

outputFormat

For each image (each set of four integers), output a single line containing a single integer: 1 if the Manhattan distance between the two black pixels is exactly K, and 0 otherwise.

sample

3 3 2
0 0 0 2
0 1 2 1
-1

1
1

</p>