CF1647C.Madoka and Childish Pranks
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
小时候的 Madoka 是个非常任性的女孩,她最喜欢的恶作剧之一就是在墙上乱画。根据 Madoka 的回忆,这面墙是一个 n 行 m 列的表格,只包含 0 和 1。第 i 行第 j 列的单元格坐标为 (i,j),其中 1≤i≤n,1≤j≤m。
有一天,她看到了“魔法少女小圆”的图片,决定把它画在墙上。最初,Madoka 的表格是一个 n×m 的全 0 表格。然后,她可以进行如下操作任意次:
Madoka 可以选择表格中的任意一个矩形子表格,并将其按照棋盘格方式涂色(子表格的左上角始终为 0)。注意,有些单元格可能会被多次涂色。在这种情况下,单元格的最终颜色等于最后一次涂色时的颜色。
白色表示 0,黑色表示 1。例如,第一张图的表格就是棋盘格涂色,其他的不是。为了更好地理解题意,建议阅读第一个测试点的讲解。
请你帮助 Madoka,找出一组不超过 n⋅m 次操作的方案,使她能够得到想要的图片,或者判断是否无法实现。
输入格式
每组测试数据包含多个测试用例。第一行包含一个整数 t(1≤t≤10),表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 m(1≤n,m≤100),表示表格的大小。接下来的 n 行,每行包含一个长度为 m 的只包含 0 和 1 的字符串,描述 Madoka 想要得到的图片。
输出格式
如果无法得到给定的图片,输出 −1。
否则,第一行输出一个整数 q(0≤q≤n⋅m),表示你需要的操作次数。注意,你不需要使操作次数最小。
接下来每行输出四个整数,表示每次操作的左上角和右下角的坐标。
输入输出样例
输入#1
4 4 5 01000 10100 01010 00110 2 3 001 010 3 3 110 101 000 1 1 0
输出#1
4 1 1 3 3 3 3 4 4 4 3 4 4 4 2 4 3 1 1 2 2 3 -1 0
说明/提示
说明/提示
第一个测试用例的描述如下。
在第三个测试用例中,无法涂出想要的图片。
在第四个测试用例中,初始表格已经是想要的图片。