# | Problem | Pass Rate (passed user / total user) |
---|---|---|
12910 | Let's build a Tetris |
|
12991 | Toad Jumping |
|
Description
You may have heard of the game Tetris Battle on Facebook,
it's was once popular and you may even have played it before.
You, after Tetris Battle closed down on May 31, 2019,
haven't played a Tetris game for a while.
Since there is no more Tetris Battle to play,
you decide to build one by yourself.
The game field of the tetris has N rows and M columns,
and there are already some piecies that is already placed on the field,
we mark them as character 'x',
and other field that hasn't been occupied by piecies are marked as character '.'.
Now, there is a falling piece, marked as 'o',
and the player want to drop the falling piece directly.
The falling piece will descend until it touch the bottom of the field,
or it land on pieces that were placed before.
If a row is completed, the row will disappear and all rows above will fall one level.
Your mission is to tell after the falling piece landed,
and all completed rows are eliminated,
what will the game field looks like?
ouo.
For sample 1,
the input is:
8 9
..o......
.oo......
..o......
.........
.........
x..xxxxxx
x..xxxxxx
xx.xxxxxx
so the falling piece will descend 5 levels until it touch the bottom of the game field, and becomes:
.........
.........
.........
.........
.........
x.oxxxxxx
xooxxxxxx
xxoxxxxxx
and since the last 2 rows are completed, so they disappear and the third row from last falls 2 levels and becomes:
.........
.........
.........
.........
.........
.........
.........
x.xxxxxxx
For sample 2,
..o...... ......... .........
..o...... ......... .........
..o...... ......... .........
..o...... ......... .........
......... ......... .........
......... => ......... => .........
......... ......... .........
xx.xxxxxx xxoxxxxxx .........
xx.xxx.xx xxoxxx.xx .........
x..xxxxxx x.oxxxxxx xxxxxx.xx
xx.xxxxxx xxoxxxxxx x.xxxxxxx
For sample 3:
....... ....... .......
...oo.. ....... .......
..oo... ....... .......
..o.... ....... .......
....... => ...oo.. => .......
.x..... .xoo... ...xx..
xx.xxxx xxoxxxx .xxx...
x.xxxxx x.xxxxx x.xxxxx
Input
The first line of the input contains 2 integers, N and M,
represent that the game field has N rows and M columns.
After that, there are N lines, each lines contains M character,
the character '.' represent that the cell is empty, not occipied,
the character 'x' represent that the cell is already placed and has been occupied,
the character 'o' represent that the cell is part of the falling piece.
It is a guaranteed that:
1 <= N, M <= 40,
the input game field will always be valid,
and all 'o' character will be connected.
Note that the shape of 'o' will may not be a normal Tetromino, it can be any shape.
Output
Output contains N lines, each line has M character,
output character '.' if the cell is empty and character 'x' if the cell is occipied.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are N stones on the river. The height of the i-th stone is hi for 1 <= i <= N and is colored with color ci. Toad Epep is on the S-th stone (where the leftmost stone is the 1-st stone) and he wants to go the the T-th stone with several jumps.
For each jump from the i-th stone, Epep can jump to the (i-1)-th stone (if it exists), the (i+1)-th stone (if it exists), or any stone colored with the same color ci (if it exists).
Epep will only visit each stone at most once. That is, if Epep jumped to the k-th stone at some time, he won't jumped to the k-th stone again.
The energy cost of jump from i-th to j-th stone is |i-j| x |hi - hj|.
Because Epep ate too much insects and wants to do more exercise, can you help Epep to find the way that cost the most energy (if there are several ways with same maximum energy cost, find the way with maximum jumps) ?
Explanation of Sample IO
All possible moves are listed in the following:
-
2 -> 1 -> 4 -> 3 -> 6 -> 5, which costs 100 energy and 5 jumps
-
2 -> 1-> 4 -> 5, which costs 60 energy and 3 jumps
-
2 -> 3-> 4-> 5, which costs 40 energy and 3 jumps
-
2 -> 3 -> 6 -> 5, which costs 40 energy and 3 jumps
-
2 -> 5, which costs 0 energy and 1 jump
Hint:
1. In this problem, you may need to use an array int jumped[N+1] to record whether a stone i has been visited in the currently expanded path.
2. However, you need to manipulate the int jumped[N+1] array properly as follows:
Input
Integers N, S, T are on the first line.
h1, ..., hN are on the second line.
c1, ..., cN are on the third line.
-
1 <= N <= 15
-
1 <= S, T <= N and S != T
-
1 <= hi <= 100000
-
1 <= ci <= 15
Test case description
-
Test case 1: all stones have different colors
-
Test case 2: all stones have the same color
-
The remaining test cases: no additional restrictions
Output
Output two integers E and J, where E is the maximum energy cost and J is the number of jumps in one line. Remember to add \n
in the end.