UVA10189

Problem B: Minesweeper

The Problem

Have you ever played Minesweeper? It's a cute little game which comes within a certain Operating System which name we can't really remember. Well, the goal of the game is to find where are all the mines within a MxN field. To help you, the game shows a number in a square which tells you how many mines there are adjacent to that square. For instance, supose the following 4x4 field with 2 mines (which are represented by an * character):

*...
....
.*..
....

If we would represent the same field placing the hint numbers described above, we would end up with:

*100
2210
1*10
1110

As you may have already noticed, each square may have at most 8 adjacent squares.

The Input

The input will consist of an arbitrary number of fields. The first line of each field contains two integers n and m (0 < n,m <= 100) which stands for the number of lines and columns of the field respectively. The next n lines contains exactly m characters and represent the field. Each safe square is represented by an "." character (without the quotes) and each mine square is represented by an "*" character (also without the quotes). The first field line where n = m = 0 represents the end of input and should not be processed.

The Output

For each field, you must print the following message in a line alone:

Field #x:

Where x stands for the number of the field (starting from 1). The next n lines should contain the field with the "." characters replaced by the number of adjacent mines to that square. There must be an empty line between field outputs.

Sample Input

4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

Sample Output

Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

解法: BFS

import java.util.Scanner;

public class UVA10189 {

 public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  int field = 0;

  while (sc.hasNext()) {

   String temp[] = sc.nextLine().split(" ");

   int n = Integer.parseInt(temp[0]);
   int m = Integer.parseInt(temp[1]);

   if (n == 0 && m == 0) {
    break;
   }

   field += 1;

   if (field > 1)
    System.out.println();

   String a = null;

   char matrix[][] = new char[n][m];

   int count_mine[][] = new int[n][m];
   

   for (int i = 0; i < n; i++) {

    a = sc.nextLine();

    for (int j = 0; j < m; j++) {

     matrix[i][j] = a.charAt(j);
     
     if (a.charAt(j) == '*')

      count_mine[i][j] = -1;
     else
      count_mine[i][j] = 0;

    }

   }

   for (int i = 0; i < n; i++) {

    for (int j = 0; j < m; j++) {

     if (count_mine[i][j] != -1) {
      int count = 0;

      for (int s = -1; s <= 1; s++) {

       for (int t = -1; t <= 1; t++) {

        if (i + s >= 0 && i + s < n && j + t >= 0
          && j + t < m)

        {

         if (matrix[i + s][j + t] == '*')
          count++;
        }

       }

      }
      count_mine[i][j] = count;
     }

    }

   }

   System.out.println("Field #" + field + ":");

   for (int i = 0; i < n; i++) {

    for (int j = 0; j < m; j++) {

     if (count_mine[i][j] != -1) {
      System.out.print(count_mine[i][j]);
     } else {
      System.out.print('*');
     }

    }
    System.out.println();
   }
  }
 }
}