网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
双面棋盘
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | dface.in | 输出文件 | dface.out |
【问题描述】
佳佳有一个 n 行 n 列的黑白棋盘,每个格子都有两面,一面白色,一面黑色。佳佳把棋盘平放在桌子上,因此每个格子恰好一面朝上,如下图所示:
|
1 |
|
|
|
|
1 |
1 |
1 |
|
1 |
|
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
我们把每行从上到下编号为 1 , 2 , 3 ,……, n ,各列从左到右编号为 1 , 2 , 3 ,……, n ,则每个格子可以用棋盘坐标 ( x , y ) 表示。在上图中,有 8 个格子黑色朝上,另外 17 个格子白色朝上。
如果两个同色格子有一条公共边,我们称这两个同色格子属于同一个连通块。上图共有 5 个黑色连通块和 3 个白色连通块。
佳佳可以每分钟将一个格子翻转(即白色变成黑色,黑色变成白色),然后计算当前有多少个黑色连通块和白色连通块,你能算得更快吗?
【 输入文件 】 dface.in
输入文件的第一行包含一个正整数 n ,为格子的边长。以下 n 行每行 n 个整数,非 0 即 1 ,表示初始状态。 0 表示白色, 1 表示黑色。下一行包含一个整数 m ,表示操作的数目。以下 m 行每行两个整数 x , y (1 ≤ x , y ≤ n ) ,表示把坐标为 ( x , y ) 的格子翻转。
【 输出文件 】 dface.out
输出文件包含 m 行,每行对应一个操作。该行包括两个整数 b , w ,表示黑色区域和白色区域数目。
【 约定 】
• 1 ≤ n ≤ 200
• 1 ≤ m ≤ 10,000
【 样例输入 】 dface.in
5
0 1 0 0 0
0 1 1 1 0
1 0 0 0 1
0 0 1 0 0
1 0 0 0 0
2
3 2
2 3
【 样例输出 】 dface.out
4 3
5 2
【 样例说明 】
翻转 (3, 2) 之后,棋盘变为:
|
1 |
|
|
|
|
1 |
1 |
1 |
|
1 |
1 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
有 4 个黑色区域和 3 个白色区域
翻转 (2, 3) 之后,棋盘变为:
|
1 |
|
|
|
|
1 |
|
1 |
|
1 |
1 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
有 5 个黑色区域和 2 个白色区域