Game sort numbers

Правка en5, от HaiZuka, 2021-02-08 13:06:28

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

_______________________________________________________________________

Let's do it with me, I'll soon create this exercise with a complete test set.

Теги #algorithms, #training

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский HaiZuka 2021-02-08 13:06:28 3 Tiny change: 'a start.\n![ ](htt' -> 'a start.\n\n![ ](htt'
en4 Английский HaiZuka 2021-02-08 13:05:13 714 Tiny change: '----\n####Input:\n####2 3 \n' -> '----\n######Input:\n######2 3 \n' (published)
en3 Английский HaiZuka 2021-02-08 12:51:50 593
en2 Английский HaiZuka 2021-02-08 12:41:51 413 Tiny change: '](https://ibb.co/8jJQ9v7)' -> '](https://www.upsieutoc.com/images/2021/02/08/a.png)'
en1 Английский HaiZuka 2021-02-08 12:21:59 831 Initial revision (saved to drafts)