http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1488. 魔法波(乔明达)
时间限制:1.0s   内存限制:256.0MB   Special Judge
总提交次数:180   AC次数:61   平均分:55.11
将本题分享到:
   
 
问题描述
  在洛丹伦大陆上,首都传来的消息让每个人都感到恐惧。带领人类军团在北方打败不死族的英雄——阿尔萨斯王子,居然刺杀了他的父亲,然后销声匿迹。在前线作战的人类士兵们失去了斗志,不死族士兵乘机进攻,打败了人类防军。洛丹伦的人类王国,剩下的只有昔日的荣耀。
  已成为死亡骑士的阿尔萨斯决定在洛丹伦上建立起不死族的基地。洛丹伦的地图可以看做一个N行N列的方格图,某些方格中是无法利用的山地,其余的方格中为空地。空地中一部分已经变成了腐地,另一部分仍然是人类的土地。因为不死族只能在腐地上建造建筑物,所以阿尔萨斯必须想办法将所有的空地变为腐地。
  阿尔萨斯决定在洛丹伦大陆上施放若干次“魔法波”。每次施放“魔法波”需要选择地图中一个代表空地(腐地或人类的土地)的格子。从这个格子出发,向上下左右四个方向发出4道魔法波,魔法波会一直朝一个方向运动,直到到达一个代表山地的格子或者移动到大陆之外。对于所有魔法波经过的格子(包括出发点的格子),其中人类的土地会变为腐地,但是腐地会变回人类的土地。需要注意的是,尽管4道魔法波都是从同一个格子出发的,但这个作为出发点的格子只会受到一次魔法的影响。此外,对于某一个格子,从这个格子出发,最多只能施放1次魔法波。

  以下是一个示例(用"X"代表山地,"1"代表腐地,"0"代表人类的土地):
  初始时的地图如下:
  00X1
  0X01
  1000
  010X
  如果在第2行第3列(行列均从1开始计数)施放“魔法波”,则施放完毕后的地图如下:
  00X1
  0X10
  1010
  011X
  注意到第2行第1列的格子并没有变化,因为第2行第2列的山地阻挡了向左的魔法波。

  现在阿尔萨斯王子需要找到一种施法方案,使得洛丹伦大陆上所有空地都变为腐地。在本题中,你可以假设这样的方案一定存在。
输入格式
  第一行包含一个数N,代表方格的行数和列数。
  以下N行,每行包含N个字符,描述了洛丹伦大陆的地图。大写字母"X"代表山地,数字"1"代表腐地,数字"0"代表人类的土地。
输出格式
  输出包含N行,每行包含N个字符。数字"1"表示需要以这个格子为出发点施放一次魔法波,数字"0"则表示不需要。对于所有代表山地的格子,相应的字符必须为"0"。
  只需要给出任意一个满足要求的方案,就可以得到这个测试点的所有分数。
样例输入
4
00X1
0X01
1000
010X
样例输出
1000
0000
0010
0000
数据规模和约定
  10%的数据满足N≤5;
  30%的数据满足N≤30;
  100%的数据满足N≤800,且地图中代表山地的格子不超过200个。