| NCTU PCCA Winter Contest 2021 |
|---|
| Finished |
Frank the shark is conducting a study on the behavior of tropical fish. During the study, he discovered an interesting species of fish, called the Gol fish, which inhabit the underwater terrain in a very bizarre way.
The Gol fish live in an area that can be represented by a square grid with $$$n$$$ rows and $$$n$$$ columns. Each square can be described as a pair $$$(i, j)$$$, where $$$i$$$ and $$$j$$$ denotes the number of the row and column it belongs to. Rows and columns are numbered from $$$0$$$ to $$$n - 1$$$. For each of the squares, there are either 0 or 1 fish living in it. Additionally, there is a sea urchin in one of the squares.
Let's define two different squares to be adjacent if they share a common edge, and be neighbors of each other if they share at least a common vertex. In each day, the following happens in order:
The "state" of all Gol fish can be described with $$$n \times n$$$ numbers, where each number denotes the amount of fish living in a square. Frank wants to conduct a experiment on the fish's behavior. Therefore, he adjusted the fish's positions so that the current state is $$$s$$$, and moved the sea urchin to $$$(r, c)$$$. He also wrote down a state $$$t$$$ that he thinks is the "ideal" state for his study, and an integer $$$d$$$. Is it possible that the state becomes $$$t$$$ in $$$d$$$ or less days?
The first line consists of two integers $$$n$$$ and $$$d$$$. The second line consists of two integers $$$r$$$ and $$$c$$$, denoting the sea urchin's location $$$(r, c)$$$.
Then $$$n$$$ lines follow, each containing $$$n$$$ digits. These lines describe the state $$$s$$$. The $$$j$$$-th digit on the $$$i$$$-th line denotes the number of fish living in the square at $$$(i, j)$$$.
Then $$$n$$$ more lines follow, each containing $$$n$$$ digits. These lines describe the state $$$t$$$. The $$$j$$$-th digit on the $$$i$$$-th line denotes the number of fish living in the square at $$$(i, j)$$$.
Technical specification:
If it's possible to reach the state $$$t$$$ from $$$s$$$ in $$$d$$$ or less days, print the string Yes. Otherwise, print No.
4 2 2 1 0100 1010 0100 0000 0100 1000 0100 0000
Yes
8 4 7 7 01000000 00100000 11100000 00000000 00000000 00000000 00000000 00000000 00000000 00100000 00010000 01110000 00000000 00000000 00000000 00000001
No
7 8 6 6 0100000 0010000 1110000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0001000 0011000 0000000 0000000
Yes
In the first example, it is possible to reach state $$$t$$$ in 2 days:

| Name |
|---|


