← 返回题目列表

AtCoder · kupc2012_8

H. 植树

中文机器翻译题面 查看原题

問題文

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) 召唤一个魔宠,你可以用树木完全覆盖森林。


作者:田村一典
测试员:花田雄一郎