CF436B Om Nom and Spiders
题目描述
奥姆诺姆真的很喜欢糖果，但他不喜欢蜘蛛，因为它们经常偷糖果。有一天，奥姆诺姆想去公园散步。不幸的是，公园里有一些蜘蛛，奥姆诺姆根本不想看到它们。
公园可以用一个n×m的矩形表示。公园里有k蜘蛛，每只蜘蛛在0点的时候都是在田野的某个牢房里。蜘蛛一直在移动，每个蜘蛛总是朝四个方向之一移动（左、右、下、上）。在一个时间单位内，一只蜘蛛从他的牢房向相应方向爬到相邻的一侧牢房。如果在指定的方向没有牢房，蜘蛛就会离开公园。蜘蛛在移动时不会互相干扰。具体来说，一个牢房可以同时有多个蜘蛛。
奥姆诺姆还不确定从哪里开始他的步行，但他肯定想要：
- 在时间为0时开始在田野的上行处行走（保证该行单元格中不包含任何蜘蛛）；
- 沿着田野向最下面一排走去（当奥姆诺姆离开公园边界时，步行结束）。
我们知道奥姆诺姆是通过跳跃来移动的。奥姆诺姆一次跳跃需要一个时间单位，小怪兽会从他的牢房到另一边相邻牢房的下一行或公园边界外。
每次Om Nom降落在一个牢房里，他都会看到此时此刻所有来到牢房的蜘蛛。omnom想要选择一个最佳的单元来开始漫游。为什么每次他都会从牢房开始走呢？帮助他计算每个可能的启动单元所需的值。
输入格式
第一行包含三个整数n，m,k(2
输出格式
打印m个整数：第j个整数必须显示从第一行的第j个单元格开始行走的蜘蛛的数目。田野中任何行中的单元格都是从左到右编号的。
说明/提示
Consider the first sample. The notes below show how the spider arrangement changes on the field over time:
`
... ... ..U ...
R.L -> .*U -> L.R -> ...
R.U .R. ..R ...
`Character "\*" represents a cell that contains two spiders at the same time. - If Om Nom starts from the first cell of the first row, he won't see any spiders. - If he starts from the second cell, he will see two spiders at time 1. - If he starts from the third cell, he will see two spiders: one at time 1, the other one at time 2.
... ... ..U ...
R.L -> .*U -> L.R -> ...
R.U .R. ..R ...
`Character "\*" represents a cell that contains two spiders at the same time. - If Om Nom starts from the first cell of the first row, he won't see any spiders. - If he starts from the second cell, he will see two spiders at time 1. - If he starts from the third cell, he will see two spiders: one at time 1, the other one at time 2.