Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2023. december 3.

December 3, 2023, 10:00 AM – December 3, 2023, 3:30 PM

Minesweeper

During the "prehistoric ages" of the internet (when there were not a lot of things to check on the web), a common game to play during the cold winter nights was the "minesweeper". For those who do not know how does the game work:

  • The playing area is a rectangle, divided into rows and columns of squares.
  • Each of the cells are clickable and the following things can happen after clicking:
    • There is a mine on that field: in this case we lose.
    • There is a number on that field, in which case the game continues. This number tells us the number of mines in the direct adjacency of the clicked cell (e.g. if the cell is not on the edge of the playing field then in the surrounding 8 cells).
  • The aim of the game is to find and defuse each mine (e.g. by right-clicking on them, but for us this is not relevant).
The aim of this exercise is to find each mine in an ASCII-minesweeper and print out their coordinates.

Input

The input consists of three units:

  • The first line contains two integers, separated by a single space characters: n and m, which tells us the number of rows and columns of the playing area respectively.
  • The next line contains a positive k integer which tells you the number of mines on the field.
  • Each of the following n lines contain a string of length m. Each character in those strings is one of the following:
    • .: there are no mines in the adjacent cells
    • 1-9: there are the given number of mines in the adjacent cells
    • ?: we know nothing about that cell

Output

The output is k lines, each one of them tells us the row and column coordinates of one unique mine. The coordinates are separated by a single space character and the first number is the row index, the second number is the column character.

Restrictions

  • n and m are at least 3 and at most 20
  • k is at least 1 and at most 20
  • the exercise is always uniquely solvable

Example

Input:
  1. 6 6
  2. 4
  3. .1???1
  4. .11211
  5. 11....
  6. ?2....
  7. ?2....
  8. 11....
download as text file Output:
  1. 0 2
  2. 0 4
  3. 3 0
  4. 4 0
download as text file
University of Debrecen; Faculty of Informatics; v. 09/30/2024