问题 3648 --飞船控制站(csapc)

3648: 飞船控制站(csapc)

题目描述

   “神州七号”飞船已经圆满发射成功了,你可知道飞船的顺利运行离不开地面对其的测控吗?因而必须保证飞船运行的轨道被测控站的雷达所全部覆盖,才能正常接受和传输信号。而由于测控站所控制的范围越小,信号接收情况越好,技术难度也越低。所以我们希望在覆盖整个轨道的前提下,使得测控站所需控制的范围越小越好。由于条件限制,最多只能建立K个测控范围相同的测控站,而且并不是任何位置都可以建立测控站的,所以需要找出一种方案,使得所需测控的范围尽量小。虽然离真正的模型还有一定差距,但喜欢编程的你当然对此问题跃跃欲试了。
 为了你的方便,已经帮你把地球抽象展开成一个N*2M的平面矩阵(N为奇数)。其中前M列是东半球,后M列是西半球,最中间的一行为赤道。为了简化问题,飞船的轨道可以看作是在一条穿越东西半球的经线上空(虽然实际并非如此),在此矩阵表示为第I列和第I+M列(1< =I< =M)两端对接形成的一个环。矩阵的每一个格子中可以建立一个监测站,但某些格子除外(比如其他国家的领土或是条件恶劣的地区)。假设测控半径为R,则每个测控站的控制范围可以向上向下各延伸R个格子,即总长度为2R+1的区间。测控范围的重叠并不会相互影响,并且显然有R> =0且2R+1< =N(因为地球是圆的,测控范围最多只能是一个半球)。
 由于飞船有M条可选轨道,所以需要你计算出对于每条轨道,最小的测控半径是多少。注意由于控制的需要,对于任意一条轨道,在东半球的赤道上都必须建立一个测控站,并且保证在东半球的赤道上建站不会有限制。

输入

输入的第一行为三个正整数N,M,K表示矩阵的大小以及测控站的数量。保证有(2< =N,M< =1000,2< =K< =2N,N为奇数)。接下来N行,每行2M个字符,如果是1则表示可以放置测控站,否则为0表示无法放置。(保证中间一行的前M个字符一定为1)

输出

输出包含M行,每行包含一个正整数,第I行表示第I条轨道所需最小的测控半径R为多少(保证必然有解),轨道从左到右依次编号。

样例输入输出

输入#1 复制
5 2 4	
0110
0000
1100
0011
1000
输出#1 复制
1
2

提示

对于轨道1:从第一行第一列开始向下可以展开为0010101001(首尾相连) 
对于轨道2:从第一行第二列开始向下可以展开为1010001000(首尾相连) 两条轨道均把可选点全部建站即可。 
数据规模: 对于30%的数据,有N,M< =15 对于60%的数据,有N,M< =100 对于100%的数据,有N,M< =1000

序号 标题 作者 发表时间 费用 订购数 操作