E. 数字华容道

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

数字华容道是一种经典的益智游戏,其规则和玩法如下:

1.游戏目标是将棋盘上的数字方块按照从左到右、从上到下的顺序重新排列整齐,例如²最后一个位置为空。玩家只能通过滑动数字方块来改变其位置,不能将方块抠下或跨越其他方块。

2.棋盘通常为的方格,例如等,其中有一个空格用于移动数字方块。数字方块的初始位置是随机打乱的,玩家需要通过滑动方块将其恢复到正确顺序。

3.每次只能将与空格相邻的数字方块滑动到空格位置,滑动后原位置变为新的空格。移动过程中,数字方块不能跨越其他方块,只能通过空格进行位置交换。

4.当所有数字方块按照从左到右、从上到下的顺序排列整齐,且最后一个位置为空时,游戏胜利。

现在你将面对一个列的数字华容道,其中各有一块。为确保公平性,正义之神将其进行随机打乱。但非常不幸的是,正义之神无法保证这个华容道是否可以被复原。请来自天外的你发挥一下你的大脑,判断其是否可以被复原。

输入格式

第一行两个正数,表示

随后行,每行个数,表示华容道每个格子里的数(0表示格子内无数字)

输出格式

输出YES或NO,表示华容道能否被复原

样例

输入 #1

2 2
1 2
3 0

输出 #1

YES

输入 #2

2 2
1 3
2 0

输出 #2

NO

数据范围与提示

数据范围 1<n,m≤1000