#P17955. Flipping Frenzy
Flipping Frenzy
Flipping Frenzy
题目描述
给定一个 行 列的二进制网格,以及 个互不相同的有序数对 。
你可以执行以下操作:
- 选择第一行或第一列中的一个格子 ,即 或 。
- 选择一个数对 。
- 翻转以 为左上角、高为 、宽为 的矩形中的全部格子:
0变成1,1变成0。
矩形必须完全位于网格内部。数对是有序的,不能自行交换矩形的高和宽。
请用不超过 次操作把网格中的所有格子变成 0。保证存在解。
输入格式
第一行一个整数 ,表示测试用例数,。
每组测试用例的第一行包含三个整数 ,满足 ,。
接下来 行,每行是一个长度为 的 01 字符串,描述网格的一行。
接下来 行,每行包含两个整数 ,满足 、。所有数对 互不相同。
所有测试用例的 之和不超过 , 之和也不超过 。每组输入均保证存在合法操作方案。
输出格式
每组测试用例先输出一个整数 ,表示操作次数,。
接下来 行,每行输出三个整数 ,表示使用第 种矩形,左上角为 。需要满足
$$1\le r_i\le k,\qquad 1\le x_i\le n-a_{r_i}+1,\qquad 1\le y_i\le m-b_{r_i}+1,$$并且 中至少一个等于 。所有下标均从 开始。
执行全部操作后,网格必须全为 0。若存在多个方案,输出任意一个即可。
样例 1
输入
5
6 6 2
000000
111110
000000
100001
011111
111110
5 5
3 5
4 5 2
10111
00101
10000
01100
1 3
2 1
2 2 1
00
00
1 1
5 5 3
10100
10010
00000
01101
00100
3 4
2 3
4 2
5 5 4
01010
01010
10101
00100
00100
2 2
2 3
3 2
3 3
输出
5
1 1 2
2 1 2
2 2 1
2 3 1
2 4 1
6
1 1 1
1 1 2
1 4 1
2 1 3
2 1 5
2 3 1
0
10
1 1 1
1 1 2
1 2 1
2 1 1
2 1 2
2 4 1
3 1 1
3 1 2
3 1 4
3 2 1
5
3 1 4
2 1 3
4 1 2
2 4 1
3 3 1