問題文
K,某大学魔法系的学生,住在一座巨大的豪宅里。 府邸后面有一片森林,但有些地方却没有树木生长。 K先生觉得从豪宅原样看去不太好看,所以他决定在没有树的地方种一棵树。 K是一名有抱负的巫师,可以召唤使魔,所以他决定让他们来做植树的工作。
林是 它可以被视为具有 H \times W 单元格的矩形区域。 每个单元格上要么长一棵树,要么不长树。 K是这个 指定 H \times W 单元格之一并在那里召唤一个魔宠。 不过,由于K还是个没有经验的人,他无法调整自己的魔力,每次召唤魔宠的时候,总是召唤出五个魔宠。 更糟糕的是,K君召唤的魔宠是反常的:如果他访问的牢房里没有树,他就会在那里种植一棵树,但如果他访问的牢房里已经长出了一棵树,他就会删除该牢房里的树。 四只召唤使魔从指定的牢房出发,沿着东西南北分散成一条直线,一一拜访各个牢房。当你离开森林时,这些使魔就会消失。 剩下的魔宠只会访问指定的单元格,然后立即消失。
更准确地说,K先生是小区 当你召唤一个魔宠到 (i, j) 时,i 行或 j 列中 对于 H+W-1 细胞, 如果没有树在生长,则种植一棵树,如果有树在生长,则删除该树。
召唤需要大量的魔力,所以我想用尽可能少的召唤来用树木覆盖森林。 K应该召唤他的魔宠到哪个格子,这样才能用最少的召唤次数将森林完全覆盖?
入力形式
输入按以下格式给出。
H\ W\ a1,1\ ...\ a1,W\ ...\ aH,1\ ...\ aH,W
ai,j 是 存在 1 然后细胞 (i,j) 表示里面长着一棵树, 0表示它没有增长。
出力形式
如果不可能用树木完全覆盖森林,那么
输出 Impossible 。
否则,创建一个召唤程序,以最小化召唤次数,格式如下:
在 H 行输出。
b1,1\ ...\ b1,W\ ...\ bH,1\ ...\ bH,W
bi,j 表示 0 或 1 必须是, 1 然后细胞 (i,j) 表示召唤一个魔宠,0 表示不召唤。
请注意,将魔宠召唤到同一位置两次是没有意义的。如果有多个召唤程序可以使召唤次数最少,则可以输出任何一个。
制約
- 2 ≤ H,W ≤ 1000
- H,W 是偶数
- ai,j \in \{0, 1\}
针对该问题的判断设置了一组3分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。
- H \times W ≤ 20
入出力例
入力例 1
4 4 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0
出力例 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
细胞 (1,1) 和细胞 通过在 (4,4) 召唤一个魔宠,你可以用树木完全覆盖森林。
作者:田村一典 测试员:花田雄一郎