Friday, January 23, 2015

10189: Minesweeper

It has been more than 5 years I guess since I last tried this problem. Last time I tried it, i always got a wrong answer. This time I tried it again after several years. as a first try, i got a wrong answer again. I then read the forums and learned that there should be no extra blank line after the last line of output. the extra blank line should only be placed between cases.

The algorithm I used was first to create an initialized array. For a 3x5 array, it would look something like this:

-------
-uuuuu-
-uuuuu-
-uuuuu-
-------

the u's above represent uninitialized data table. they can be random initially. but notice that after initialization, you have dash characters surrounding the data table.

we then read the input into the array:

-------
-**...-
-.....-
-.*...-
-------

we then process each element in the data table one element at a time.

First we process the first element. for each element, we consider the 3x3 matrix surrounding the element under consideration:

-------
-**...-
-.....-
-.*...-
-------


for this 3x3 matrix, we count the number of asterisk characters which represent bombs.

Then we consider the next element and its corresponding 3x3 matrix:


-------
-**...-
-.....-
-.*...-
-------


again we count the number of bombs for this 3x3 matrix.

we do this process again and again until we process the last element in the data table:


-------
-**...-
-.....-
-.*...-
-------


In processing the cases, just be careful that you do not print an extra line after the last case. One way to do this is to get dimensions from the user first. Then enter the while-loop. In the while loop, process the data, then get the dimensions from the user. if the dimensions are not both zero, then print an extra line before looping back to the start of the while-loop.

One thing I did was not to use the gets() function anymore to get lines from the user input. I installed ubuntu 14.01 onto my netpad and when I compiled the code using g++, I get a warning message saying that the use of gets() is unsafe. Therefore, I have returned to my usual way of getting input from the user: using the fgets() function.

     1    #include "stdio.h"
      
     2    int main() {
     3      int n, m;
     4      int i, j;
     5      int p, q;
     6      int count, field;
     7      char arr[150][150];
     8      char line[150];
      
     9      for (i = 0; i < 150; i += 1) {
    10        arr[i][0] = '-';
    11        arr[0][i] = '-';
    12      }
      
    13      fgets(line, 150, stdin);
    14      sscanf(line, "%d %d\n", &n, &m);
    15      if (n == 0 && m == 0) {
    16        return 0;
    17      }
      
    18      for(field = 1; 1; field += 1) {
    19        for (i = n + 1, j = 1; j <= m + 1; j += 1) {
    20          arr[i][j] = '-';
    21        }
      
    22        for (i = 1, j = m + 1; i <= n + 1; i += 1) {
    23          arr[i][j] = '-';
    24        }
      
    25        for (i = 1; i <= n; i += 1) {
    26          fgets(line, 150, stdin);
    27          for (j = 0; j < m; j += 1) {
    28            arr[i][j+1] = line[j];
    29          }
    30        }
      
    31    //    for (i = 0; i <= n + 1; i += 1) {
    32    //      for (j = 0; j <= m + 1; j += 1) {
    33    //        printf("%c", arr[i][j]);
    34    //      }
    35    //      printf("\n");
    36    //    }
    37    //    printf("\n");
      
    38        printf("Field #%d:\n", field);
    39        for (i = 1; i <= n; i += 1) {
    40          for (j = 1; j <= m; j += 1) {
    41            if (arr[i][j] == '*') {
    42              printf("%c", '*');
    43            }
    44            else {
    45              count = 0;
    46              for (p = i - 1; p <= i + 1; p += 1) {
    47                for (q = j - 1; q <= j + 1; q += 1) {
    48                  if (arr[p][q] == '*') {
    49                    count += 1;
    50                  }
    51                }
    52              }
    53              printf("%d", count);
    54            }
    55          }
    56          printf("\n");
    57        }
      
    58        fgets(line, 150, stdin);
    59        sscanf(line, "%d %d\n", &n, &m);
      
    60        if (n == 0 && m == 0) {
    61          break;
    62        }
      
    63        printf("\n");
    64      }
      
    65      return 0;
    66    }

No comments:

Post a Comment