1013: 湖南省第十七届大学生计算机程序设计竞赛(HNCPC2021) - Semilive
Start Time:2021-12-05 18:00:00 End Time:2021-12-05 23:00:00 Current Time:2025-05-12 03:18:29 Public Ended
B (1158) : 方格填数
Time Limit: 1 Sec Memory Limit: 128 MB Submitted: 126 Solved: 32Description
Alice和Bob在玩方格填数游戏,他们需要在n行m列共n ⋅ m个方格中填入1到n ⋅ m,并且需要满足以下几个条件:
- 每个格子填一个数,任意两个格子的数均不相同;
- 对于任意相邻两个格子,右边格子的数需要大于左边格子的数,下边格子的数需要大于上边格子的数。
方格由上至下依次为第1行,第2行,…,第n行,由左至右依次为第1列,第2列,…,第m列。
Alice首先在方格中填入了一个数,现在Bob想知道是否仍然存在至少一种方案使得Bob可以填完剩下的数并且满足上述条件。
Input
包含多组测试数据。
每组测试数据的第一行包含两个整数n、m,中间用一个空格隔开。 其中,2 ≤ n ≤ 1000,2 ≤ m ≤ 1000。
接下一行包含三个整数r、c、v,表示Alice在第r行c列的格子中填了v。 其中,1 ≤ r ≤ n,1 ≤ c ≤ m,1 ≤ v ≤ n ⋅ m。
Output
对于每组测试数据,如果存在至少一种方案使得Bob可以填完剩下的数并且满足上述条件,输出“Yes”,否则输出“No”。
Sample
2 3 1 3 2 2 3 2 2 4
No Yes
Hint
两组测试数据Alice填完后方格的状态分别为:
-- -- -- -- -- --
| | |2 | | | | |
-- -- -- -- -- --
| | | | | |4 | | -- -- -- -- -- --
对于第二组数据,存在如下两种方案使得Bob可以填完剩下的数并且满足上述条件:
-- -- -- -- -- --
|1 |3 |5 | |1 |2 |5 |
-- -- -- -- -- --
|2 |4 |6 | |3 |4 |6 | -- -- -- -- -- --