Rebel Die

The rebel die needs to escape from the board prison. To accomplish the escape it needs to blend in with the board on its way. Unfortunately, the guards colored the board using various colors and figuring out the correct camouflage seems very difficult. The die is trying to get from the top-left corner square to the bottom-right corner square. Fortunately, its sides are of the same size as the squares of the grid and each grid square is colored by a single color. The die wants to color its sides to blend in. The only moves it can do is to flip (along an edge) onto one of the neighboring squares (for most squares there are four neighboring squares). To go unnoticed the top color of the die must always match the color of the square on which it is (in particular, in the starting position the top color of the die must match the color of the top-left corner square and in the final position the top color of the die must match the color of the bottom-right corner square). The die cannot do any other moves (for example, it cannot rotate on a square). Please help the die to figure out if a good camouflage exists.

\includegraphics[width=0.5\textwidth ]{rebeldie}
Figure 1: For the first sample input, the coloring for the rebel die is shown below on a cube net. This is the only camouflage that allows the die to get from the top-left corner to the bottom-right corner and there is only one way how to do so.


The first line contains two integers $m$ (the height of the board) and $n$ (the width of the board). Then $m$ lines follow. Each of the $m$ lines contains $n$ integers. Each integer encodes a color. Assume that $1 \leq m, n \leq 100$ and the colors are integers from $\{ 0, 1, \ldots , 29\} $.


The output contains one line with “YES” if there exists a coloring of the die that allows the die to flip from the top-left corner square (the square in first column of the first row) to the bottom-right corner square (the square in the last column of the last row) on that board. If such a coloring does not exist then the line contains “NO”.

Sample Input 1 Sample Output 1
4 4
0 1 2 3
0 4 0 0
2 4 1 4
5 6 7 8
Sample Input 2 Sample Output 2
4 4
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6
CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 8.8hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in