CF1700E

· · 题解

不难想，但有点卡常，差评。

首先把可解的概念分析一下，容易发现就是对于 2 到 n\times m，与它相邻的四个格子中至少有一个数比它小。

先把 0 的情况判掉。

容易发现一次交换至多只会让 4 个不合法的格子变得合法，因此先统计不合法的格子，如果个数大于 4 个直接输出 2 即可。

然后容易发现被交换的两个格子中至少有一个是不合法的格子或者是和不合法的格子相邻的格子，这个个数最多是 4\times 5= 20 个。

然后第一次先枚举这 20 个，第二层再暴力枚举 n\times m 个，每次只需要检查受交换影响的格子就可以了。

复杂度是 O(nm) 级别的，有差不多 20\times30 的常数，但是剪剪枝必然跑不满，可以过。

丑陋的代码