CF1647C.Madoka and Childish Pranks

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

小时候的 Madoka 是个非常任性的女孩,她最喜欢的恶作剧之一就是在墙上乱画。根据 Madoka 的回忆,这面墙是一个 nnmm 列的表格,只包含 0011。第 ii 行第 jj 列的单元格坐标为 (i,j)(i, j),其中 1in1 \le i \le n1jm1 \le j \le m

有一天,她看到了“魔法少女小圆”的图片,决定把它画在墙上。最初,Madoka 的表格是一个 n×mn \times m 的全 00 表格。然后,她可以进行如下操作任意次:

Madoka 可以选择表格中的任意一个矩形子表格,并将其按照棋盘格方式涂色(子表格的左上角始终为 00)。注意,有些单元格可能会被多次涂色。在这种情况下,单元格的最终颜色等于最后一次涂色时的颜色。

白色表示 00,黑色表示 11。例如,第一张图的表格就是棋盘格涂色,其他的不是。为了更好地理解题意,建议阅读第一个测试点的讲解。

请你帮助 Madoka,找出一组不超过 nmn \cdot m 次操作的方案,使她能够得到想要的图片,或者判断是否无法实现。

输入格式

每组测试数据包含多个测试用例。第一行包含一个整数 tt1t101 \le t \le 10),表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 nnmm1n,m1001 \leq n, m \leq 100),表示表格的大小。接下来的 nn 行,每行包含一个长度为 mm 的只包含 0011 的字符串,描述 Madoka 想要得到的图片。

输出格式

如果无法得到给定的图片,输出 1-1

否则,第一行输出一个整数 qq0qnm0 \leq q \leq n \cdot 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

说明/提示

说明/提示

第一个测试用例的描述如下。

在第三个测试用例中,无法涂出想要的图片。

在第四个测试用例中,初始表格已经是想要的图片。

首页