No.2657 Falling Block Game
タグ : / 解いたユーザー数 51
作問者 : 👑
hamamu
/ テスター :
👑 
てんぷら
Problem Statement
There is a computer game in which you steer a ball falling from the top to the bottom of the screen left and right, dodging obstacles to reach the bottom.
The game screen is represented by a grid with height $H$ and width $W$.
The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$.
At time $0$, the ball appears at a random cell in the top row,
and every $1$ second it instantly moves to the cell one below.
That is,
for $t=1,2, \cdots ,H-1$,
at time $t$ it instantly moves from $(t,j)$ to $(t+1,j)$.
Also, when the ball is at $(i,j)$, if the player presses the left button it instantly moves to $(i,j-1)$,
and if the player presses the right button it instantly moves to $(i,j+1)$.
However, the downward move and a left or right move cannot be done simultaneously (that is, diagonal moves are not possible).
Also, the ball cannot move outside the grid.
Whether cell $(i,j)$ has an obstacle is represented by the character $S_{i,j}$.
If $S_{i,j}=$#, there is an obstacle, and if it is ., there is no obstacle.
If the ball moves to a cell with an obstacle, the game is over.
If the ball moves to any cell in the bottom row without the game being over, the game is cleared.
The top row and the bottom row have no obstacles.
Also, the obstacles are never arranged in a way that makes the game impossible to clear.
Since hamamu has tendinitis,
hamamu wants to clear the game while minimizing the maximum number $P$ of button presses per second.
Formally,
for $t=1,2, \cdots ,H-1$, let $f(t)$ be the number of button presses between time $t-1$ and time $t$,
and let $$P=\max_{t=1,2,\cdots,H-1} f(t)$$;
hamamu wants to minimize $P$.
For each $k=1,2, \cdots ,W$, find the minimum value of $P$ when the ball appears at cell $(1,k)$.
Constraints
- $3 \le H \le 10^5$
- $1 \le W \le 10^5$
- $HW \le 5\times 10^5$
- $S_{1,j},S_{H,j} (1 \le j \le W)$ are all
. - The game can be cleared no matter which cell the ball appears at at time $0$
- $H,W$ are integers
- $S_{i,j}$ is
.or#
Input
The input is given from standard input in the following format.$H\ W$
$S_{1,1}S_{1,2} \cdots S_{1,W}$
$S_{2,1}S_{2,2} \cdots S_{2,W}$
$\cdots$
$S_{H,1}S_{H,2} \cdots S_{H,W}$
Output
Output $W$ lines.
On the $k$-th line, output the minimum value of $P$ when the ball appears at cell $(1,k)$.
Print a newline at the end.
Sample
Sample 1
Input
3 3 ... ##. ...
Output
2 1 0
When $k=1$, the ball appears at cell $(1,1)$ at time $0$.
Pressing the right button $2$ times between time $0$ and time $1$ moves it to cell $(1,3)$.
At time $1$, it moves to cell $(2,3)$.
At time $2$, it moves to cell $(3,3)$ and reaches the bottom row, so the game is cleared.
Here, $f(1)=2,f(2)=0$, and $P=2$.
There is no way to clear the game with $P \lt 2$, so the answer is $2$.
Similarly, the minimum values of $P$ for $k=2,3$ are $1,0$, so output them.
Sample 2
Input
4 3 ... ... ##. ...
Output
1 1 0
We explain only the case $k=1$.
The ball appears at cell $(1,1)$ at time $0$.
Pressing the right button $1$ time between time $0$ and time $1$ moves it to cell $(1,2)$.
At time $1$, it moves to cell $(2,2)$.
Pressing the right button $1$ time between time $1$ and time $2$ moves it to cell $(2,3)$.
At time $2$, it moves to cell $(3,3)$.
At time $3$, it moves to cell $(4,3)$ and reaches the bottom row, so the game is cleared.
Here, $f(1)=1,f(2)=1,f(3)=0$, and $P=1$.
There is no way to clear the game with $P \lt 1$, so the answer is $1$.
Sample 3
Input
5 8 ........ .######. ........ ##...### ........
Output
2 2 2 3 3 3 3 3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。