Minesweeper is a computer game that became popular in the 1980s, and is still included in some versions of the Microsoft Windows operating system. This problem has a similar idea, but it does not assume you have played Minesweeper.
In this problem, you are playing a game on a grid of identical cells. The content of each cell is initially hidden. There are M mines hidden in M different cells of the grid. No other cells contain mines. You may click on any cell to reveal it. If the revealed cell contains a mine, then the game is over, and you lose. Otherwise, the revealed cell will contain a digit between 0 and 8, inclusive, which corresponds to the number of neighboring cells that contain mines. Two cells are neighbors if they share a corner or an edge. Additionally, if the revealed cell contains a 0, then all of the neighbors of the revealed cell are automatically revealed as well, recursively. When all the cells that don't contain mines have been revealed, the game ends, and you win.
For example, an initial configuration of the board may look like this ('*' denotes a mine, and 'c' is the first clicked cell):
*..*...**. ....*..... ..c..*.... ........*. ..........
There are no mines adjacent to the clicked cell, so when it is revealed, it becomes a 0, and its 8 adjacent cells are revealed as well. This process continues, resulting in the following board:
*..*...**. 1112*..... 00012*.... 00001111*. 00000001..
At this point, there are still un-revealed cells that do not contain mines (denoted by '.' characters), so the player has to click again in order to continue the game.
You want to win the game as quickly as possible. You want to find the minimum number of clicks to win the game. Given the size of the board (N x N), output such minimum number of clicks.The first line of the input gives the number of test cases, T. Ttest cases follow. First line of each test case contains one integer N. N lines strings with length N follows containing '*' and '.', denotes the Minesweeper initial board.
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of clicks to win.
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ N ≤ 50.
1 ≤ N ≤ 300.
2 3 ..* ..* **. 5 ..*.. ..*.. .*..* .*... .*...
Case #1: 2 Case #2: 8
Tom is taking metros in the city to go from station to station.
The metro system in the city works like this:
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with an integer N, the number of metro lines. N metros descriptions follow. Each metro description starts with two integers SNi and Wi, the number of stations and the expected waiting time in minutes. The next line consists of SNi-1 integers, Timei,1, Timei,2, ..., Timei,SNi-1, describing the travel time between stations.
After the metro descriptions, there is an integer M, the number of tunnels. M lines follow to describe the tunnels. Each tunnel description consists of 5 integers, m1i, s1i, m2i, s2i, ti which means the tunnel is connecting stations Sm1i,s1i and station Sm2i,s2i. The walking time of the tunnel is ti.
The next line contains an integer Q, the number of queries.
Each of the next Q lines consists of 4 integers, x1, y1, x2, y2, which mean you are going to travel from station Sx1,y1 to station Sx2,y2.
For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1), then followed by Q lines, each line containing an integer y which is the shortest time you need for that query. If it's impossible, output -1 for that query instead.
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ Wi ≤ 100.
1 ≤ Timei,j ≤ 100.
1 ≤ m1i ≤ N.
1 ≤ s1i ≤ SNm1i.
1 ≤ m2i ≤ N.
1 ≤ s2i ≤ SNm2i.
m1i and m2i will be different.
1 ≤ ti ≤ 100.
1 ≤ Q ≤ 10.
1 ≤ x1 ≤ N.
1 ≤ y1 ≤ SNx1.
1 ≤ x2 ≤ N.
1 ≤ y2 ≤ SNy2.
Station Sx1,y1 and station Sx2,y2 will be different.
1 ≤ N ≤ 10.
0 ≤ M ≤ 10.
2 ≤ SNi ≤ 100.
The total number of stations in each case is at most 100.
1 ≤ N ≤ 100.
0 ≤ M ≤ 100.
2 ≤ SNi ≤ 1000.
The total number of stations in each case is at most 1000.
2 2 5 3 3 5 7 3 4 2 1 1 1 1 1 2 2 2 1 1 1 1 2 4 2 5 3 3 5 7 3 4 2 1 1 1 2 1 2 2 2 1 2 4 1 4 1 1 1 1 1 5
Case #1: 11 Case #2: 18
In the first case, you are going to travel from station 1 of metro line 1 to station 4 of metro line 2. The best way is:
Alice is a smart student who is very good at math. She is attending a math class. In this class, the teacher is teaching the students how to use a calculator. The teacher will tell an integer to all of the students, and the students must type that exact number into their calculators. If someone fails to type the number, he or she will be punished for failing such an easy task!
Unfortunately, at the beginning of the class, Alice finds that her calculator is broken! She finds that some of the number buttons are totally broken, and only the "multiply" and "equals" operator buttons are available to use. So she can only use these buttons to get the number quickly.
For instance, the teacher may say the number "60", while Alice's calculator can only type "1", "2" and "5". She could push the following buttons:
The first line of the input gives a number T, the number of integers the teacher says. T test cases follow.
Each case contains two lines. The first line contains ten numbers each of which is only 0 or 1. the ith number (starting from 0) is "1" if the number i can be clicked, or "0" if it is broken. The second line contains only one number X, the integer the teacher tells everyone.
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of button clicks needed, or "Impossible" if it is not possible to produce the number.
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ X ≤ 100.
1 ≤ X ≤ 106.
3 0 1 1 0 0 1 0 0 0 0 60 1 1 1 1 1 1 1 1 1 1 128 0 1 0 1 0 1 0 1 0 1 128
Case #1: 5 Case #2: 4 Case #3: Impossible
The first sample case is explained in problem statement.
In the second case, all digits are available, so Alice can just press "1", "2", "8" and then "equals" to get the result. Please note that she still needs to press "equals" in the last step, even though there are no calculations.
For the last case, it's impossible since Alice cannot input any even numbers.
Tetris is a famous video game that almost everyone has played it. In this problem, you need to simulate a simplified version of it.
In our version, the game is played in a W by H field with gravity. At the beginning, the field is empty. Then the tetrominos start to fall from above top of the field to bottom of the field, one by one. Each tetromino will stop as soon as it touches some other tetrominos or bottom of the field.
One interesting feature of the game is called "line clearing". A line will be cleared as soon as it is filled by tetrominos. More than one line may be cleared at a time. For example:
|..............| |..............| |..............|
|.............o| |..............| |..............|
|.............o| |..............| |..............|
|.............o| |..............| |..............|
|.............o| |..............| |..............|
|..xx..........| --> |..xx..........| --> |..............|
|xxxxxxxxxxxxx.| |xxxxxxxxxxxxxo| |..............|
|xxxxxxxxxxxxx.| |xxxxxxxxxxxxxo| |..xx..........|
|xx..xxxxxxxxx.| |xx..xxxxxxxxxo| |xx..xxxxxxxxxo|
|xxxxxxxxxxx...| |xxxxxxxxxxx..o| |xxxxxxxxxxx..o|
---------------- ---------------- ----------------
Falling Stopped Cleared 2 lines
Note that in this simplified version, the "floating" tetromino blocks won't continue to fall after lines are cleared. This is why the top-most two squares will keep in such position. Consequently, cascade clearing won't happen, even though it would happen in the original version of Tetris.
The game ends when all the given tetrominos are placed, or the current tetromino cannot be placed due to the height limit of the field is reached.
In this problem, each tetromino will has its type, rotation and falling position told by the input. They will start to fall from the above of the field. Your goal is to simulate and get the final result of each play.
We have 7 types of tetromino:
1 2 3 4 5 6 7
x x x x xx x x
xx xx x x xx x xxx
x x xx xx x
x
Rotation of a tetromino is represented by a number r. r can be 0, 1, 2 or 3. Rotation is counterclockwise. For example:
r=0 r=1 r=2 r=3
x x xxx x
xxx xx x xx
x x
x xx x xx
xx xx xx xx
x x
The horizontal falling position is represented by a number x. It is the coordinate of the lower left square of a tetromino's bounding box. Here x starts from 0.
The first line of the input gives the number of test cases, T. For each test case, the first line of input has 3 integers, W, H, N. W is the width, H is the height and N is the number of blocks that are going to fall.
Then N lines below, each line has 3 integers, ti, ri, xi. ti tells the tetromino type. ri is the rotation of this tetromino. xi is the horizontal falling position of this tetromino. It is guaranteed that xi will make the tetromino inside the field, horizontally.
For each test case, first output one line containing "Case #i:", where i is the test case number (starting from 1). And then, if the game ends before the N blocks, output "Game Over!"(without quotes). Otherwise, output the game field's final state, which should have H lines, each has W characters. Each character can be '.' or 'x'.
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 <= T <= 100
1 <= ti <= 7
0 <= ri < 4
4 <= W <= 20
1 <= H <= 20
0 <= N <= 100
4 <= W <= 100
1 <= H <= 100
0 <= N <= 5000
5 8 6 1 1 0 0 5 4 1 1 1 1 5 6 3 5 0 0 5 0 2 3 2 3 6 4 3 6 2 0 6 2 0 6 2 0 6 4 2 6 0 0 6 0 1
Case #1: ........ ........ ........ x....... xx...... .x...... Case #2: ..... ..... ..xx. .xx.. Case #3: ..... ..... ..... ..... ..... ...xx Case #4: Game Over! Case #5: xx.... xx.... xx.... xx....