407939: GYM102946 F Fishy Study

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:

1. The sea urchin moves to a square that is adjacent to the one it is currently in.
2. The Gol fish's ecosystem updates itself to a new generation. For each square in the grid:
   • If the sea urchin is in this square, then no fish will live in it in the next generation.
   • Otherwise, if it has a fish in it, and exactly 2 or 3 neighbors have fish in them, then there will be a fish in this square in the next generation.
   • Otherwise, if exactly 3 neighbors have fish in them, then there will be a fish in this square in the next generation.
   • Otherwise, there will be no fishing living in it in the next generation.
   The update happens for every square at the same time.

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:

• $$$2 \le n \le 8$$$
• $$$0 \le d \le 8$$$
• Each digit describing $$$s$$$ and $$$t$$$ is either 0 or 1.

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: