VPL2_BC - Peter Quest

no tags 

Is Peter’s birthday! And his friends are preparing a big party, however, Peter is obsessed with a variation of the famous game Minesweeper, moreover, Peter hates losing, so if any of you or your friends can beat him in the game, he will get angry and will attend the party that everyone is organizing for him.

This new mode of Minesweeper consists in building the gameboard given the mines, so, if the matrix has size of (2×2) and there is a mine in the position (0, 0) of the matrix, the resultant gameboard will be *1 11 Your task is to beat Peter and celebrate his birthday before its too late! Please have in consideration that:

  • The cell (i, j) where there is a mine will be denoted as ’*’.
  • The cell (i, j) where there is no mine will be denoted as ’-’.
  • The cell (i, j) where there is N mines adjacent to it, will be denoted as a number from 1 to 8 (depending on the number of adjacencies.)

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

For each test case, you will have a line with three numbers N, M, K, denoting, respectively, the size of the matrix, formed by N columns and M rows, and K mines. Then, K lines will follow, each containing two numbers Ki and Kj denoting the position where the mine is in the board.

Output

For each test case you should print the string "Scenario #i:" where i represents the test case you are analyzing (starting from 1), then, in the next line, you shall print the gameboard as specified.

Example

Input:
3
3 2 2
0 0
1 1
3 3 3
0 0
1 1
2 2
8 8 10
0 1
5 0
2 5
4 5
2 6
5 6
6 6
5 7
6 7
7 7

Output:
Scenario #1:
*2
2*
11
Scenario #2:
*21
2*2
12*
Scenario #3:
1*1-----
111-1221
----1**1
----2331
11--1*32
*1--13**
11---2**
-----13*

Constraints

Subtask 1 (10%)
  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 8
  • 1 ≤ K ≤ min(8, N×M)
Subtask 2 (20%)
  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 128
  • 1 ≤ K ≤ min(128, N×M)
Subtask 3 (30%)
  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 1024
  • 1 ≤ K ≤ min(1024, N×M)
Subtask 4 (40%)
  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 6144
  • 1 ≤ K ≤ min(100000, N×M)

hide comments
nadstratosfer: 2020-02-07 02:01:13

AC with a pure (interpreted) Python means any problems with TL are purely down to implementation.

The new C compilers suck though; based on my experiments with similar problems, my current 0.33s would have come in under 0.15s half year ago :( Zukow, if you're reading this, how fast does your top solution run today?

Last edit: 2020-02-07 02:03:11
ankit kumar: 2015-06-12 14:16:32

wow.. felt good

anurag garg: 2013-12-18 08:46:16

nice problem...good implementation

Last edit: 2013-12-18 08:46:43
Ouditchya Sinha: 2013-08-15 12:33:55

Nice problem, another fastest solution for me. :)

Garg Ankit: 2013-07-29 20:50:20

@Mostafa
It works like a charm for all these examples as well as a few cases of mine.

Mostafa 36a2: 2013-07-28 18:00:37

@Garg Ankit
there is no spaces between adjacent cells.
have you tried your code on the example ?

Garg Ankit: 2013-07-28 11:56:29

Any tricky test case?
Dunno why, but I am getting WA.
What about the whitespaces in the answer format? Does each testcase output ends with a blank line?

Last edit: 2013-07-28 12:01:14
Mostafa 36a2: 2013-07-28 09:46:03

OUCH , just one letter in my code cost me 10 WA :D

biQar: 2013-07-15 07:56:46

I have doubt about the Time Limit for Java solutions. Problem-setter should check that. I am waiting for the response.

I got AC by submitting in C++, I think Java Time Limit is too strict. Java Time Limit need to be changed !

Last edit: 2013-08-02 05:32:25
BLANKRK: 2013-07-08 17:41:16

wow!! got AC in fst attmpt.... :D


Added by:Venezuelan Programming League
Date:2013-06-29
Time limit:5s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64