I saw multiple solutions of this task and wanted to share mine, which is suboptimal but can still pass.
My Solution
First, we use $$$H+W$$$ OR gates to connect each row and column together.
Now, we will find the horizontal and vertical distance between the two points then add it up. If we check all pairs of rows and columns, we will use $$$\mathcal{O}(H^2 + W^2)$$$ gates which will solve $$$H, W \leq 30$$$ and will use just a bit too much for $$$H, W \leq 100$$$.
Consider the problem in one dimension. Rather than trying to create a circuit for each possible distance, we will find the binary representation of the distance. For each bit $$$b$$$, we can check if the distance in some direction has the $$$b$$$-th bit on. This is doable by considering OR(AND($$$i$$$, OR($$$i+k$$$))) for all $$$i, k$$$ that $$$k$$$ has the $$$b$$$-th bit on . This uses $$$\mathcal{O}(H \log H + W \log W)$$$ gates.
Now that we have the horizontal and vertical distance in binary, we can implement a binary adder circuit, then check if the resulting value is $$$K$$$ or not.
Комментарии (0)
