P4121 [WC2005] 双面棋盘

题目描述

佳佳有一个 $n$ 行 $n$ 列的黑白棋盘,每个格子都有两面,一面白色,一面黑色。佳佳把棋盘平放在桌子上,因此每个格子恰好一面朝上,如下图所示: ![](https://cdn.luogu.com.cn/upload/image_hosting/rcejbuct.png) 我们把每行从上到下编号为 $1$,$2$,$3$,……,$n$,各列从左到右编号为 $1$,$2$,$3$,……,$n$,则每个格子可以用棋盘坐标$(x, y)$表示。在上图中,有 $8$ 个格子黑色朝上,另外 $17$ 个格子白色朝上。 如果两个同色格子有一条公共边,我们称这两个同色格子属于同一个连通块。上图共有 $5$ 个黑色连通块和 $3$ 个白色连通块。 佳佳可以每分钟将一个格子翻转(即白色变成黑色,黑色变成白色),然后计算当前有多少个黑色连通块和白色连通块,你能算得更快吗?

输入格式

输出格式

说明/提示

【样例说明】 翻转 $(3, 2)$ 之后,棋盘变为: ![](https://cdn.luogu.com.cn/upload/image_hosting/9oqt0zsv.png) 有 $4$ 个黑色区域和 $3$ 个白色区域 翻转 $(2, 3)$ 之后,棋盘变为: ![](https://cdn.luogu.com.cn/upload/image_hosting/f335hulm.png) 有 $5$ 个黑色区域和 $2$ 个白色区域 【数据范围】 对于 $100\%$ 的数据,$1\le n \le 200$,$1\le m \le 10^4$。