瞎扯淡 Google CodeJam 开始啦~赶快来玩

ruohanc · April 12, 2014 · Last by chunlea replied at April 13, 2014 · 2964 hits

我也是第一次接触,给大家一个 quick-start:

  1. 选择题目之后先看题干,写好代码后点下图的 Solve 按钮
  2. 会自动下载一个 Input file 给你,然后你用这个 input file 计算出 output
  3. 把 output 和 source code 两个文件上传
  4. 继续下一题

第一轮还挺简单的~ 我就第三题不会做。

http://code.google.com/codejam/

第三题

Problem

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. There is nothing quicker than winning in one click. Given the size of the board (R x C) and the number of hidden mines M, is it possible (however unlikely) to win in one click? You may choose where you click. If it is possible, then print any valid mine configuration and the coordinates of your click, following the specifications in the Output section. Otherwise, print "Impossible".

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains three space-separated integers: R, C, and M.

Output

For each test case, output a line containing "Case #x:", where x is the test case number (starting from 1). On the following R lines, output the board configuration with C characters per line, using '.' to represent an empty cell, '*' to represent a cell that contains a mine, and 'c' to represent the clicked cell.

If there is no possible configuration, then instead of the grid, output a line with "Impossible" instead. If there are multiple possible configurations, output any one of them.

Limits

0 ≤ M < R * C.

Small dataset

1 ≤ T ≤ 230.
1 ≤ R, C ≤ 5.

Large dataset

1 ≤ T ≤ 140.
1 ≤ R, C ≤ 50.

Sample

Input 

5
5 5 23
3 1 1
2 2 1
4 7 3
10 10 82
Output 

Case #1:
Impossible
Case #2:
c
.
*
Case #3:
Impossible
Case #4:
......*
.c....*
.......
..*....
Case #5:
**********
**********
**********
****....**
***.....**
***.c...**
***....***
**********
**********
**********

这个时间限制是一道题只准 8 分钟内就要做对?

#1 楼 @bhuztez 不是....8 分钟内提交答案的意思。

就是说可以先写好程序,然后点 solve 拿到 input, 接着用你的电脑计算个七分钟,算出答案后上传就行了....

#2 楼 @ruohanc 八分钟内不能提交一个正确答案,就没机会了?

这个不是可以随便玩的,怕怕!

#3 楼 @bhuztez 是啊..B 大 - -........

small input 可以尝试多次,但是失败会有 panalty, large input 只有一次机会,八分钟内提交,以最后一次的为准

#5 楼 @ruohanc 这也太刺激了,我还是等先学会点算法再说吧

召唤 @luikore 我第三题解不出来...给个思路嘛~

You need to Sign in before reply, if you don't have an account, please Sign up first.