Hello codeforces. Today I have a very interesting exercise, which is a number sorting game. First of all, let's understand this game.
The interface will consist of a rectangle of m rows and n columns, containing m * n squares of size 1*1. The squares will get a value from 1 to m*n-1 where no 2 cells have the same value, and 1 empty cell is numbered -1. For each step, the player is allowed to change the position of the empty cell (_containing the number -1_) for the adjacent cells. The game will be over if the tiles are in place, an empty cell (bearing number -1) is at the bottom right corner, the remaining numbers are arranged in ascending order from left to right, top to bottom. The figure below is an example of the ending game:
Given before starting game state check if you can end the game, output "YES" if possible, otherwise return "NO".
Input
- The first is two integers m and n, which are the dimensions of the matrix. (**1 < m, n < 10000**)
- Next is the values of the elements in the matrix.
Output
Returns "YES" if it can be sorted to end state, otherwise "NO".
Examples
----------------------------------------------------------------------- Input: 2 3 1 5 2 4 3 -1 Output: YES
The game can be over, the bottom one is to end the game. 
----------------------------------------------------------------------- Input: 2 2 1 3 2 -1 Output: NO
There is no way to end a game with such a start. 
----------------------------------------------------------------------- Input: 3 3 2 7 1 4 6 3 5 -1 8 Output: NO
