1  
   2  /* 
   3   * A solution for the Minesweeper problem.
   4   * UVa ID: 10189
   5   */
   6  #include <stdio.h>
   7  
   8  #define MINE '*'
   9  #define MATRIX_OFFSET 1
  10  
  11  int main (int argc, const char * argv[]) {
  12  	/* number of lines of the mine field */
  13  	long n;
  14  	
  15  	/* number of colums of the mine field */
  16  	long m;
  17  	
  18  	/* iterators for retrieving the content of each field line*/
  19  	long i, j;
  20  	
  21  	/* field number identifier */
  22  	long fieldNumber = 0;
  23  
  24  	while(scanf("%ld %ld", &n, &m) != EOF) {
  25  			
  26  		/* 0 0, ends the program */
  27  		if (!n && !m) {
  28  			return 0;
  29  		} else {
  30  			if (fieldNumber > 0) {
  31  				/* 
  32  				 * workaround for the extra line on the output, 
  33  				 * which was giving me a Wrong Answer verdict..
  34  				 * so only insert an extra line if there's more
  35  				 * to come :-) 
  36  				 */
  37  				printf("\n");
  38  			}
  39  		}
  40  		
  41  		/* increment field id */
  42  		fieldNumber++;
  43  				
  44  		/* a bidimensional array representing the input mine field */
  45  		char inputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
  46  		
  47  		/* a bidimensional array to output the mine field */
  48  		int outputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
  49  		
  50  		/* temporary variable to retrieve mine field lines */
  51  		char line[m];
  52  		
  53  		/* init, O(n2) */
  54  		for (i = 0; i < n + MATRIX_OFFSET + 1; i++) {
  55  			for (j = 0; j < m + MATRIX_OFFSET + 1; j++) {
  56  				outputField[i][j] = 0;
  57  			}
  58  		}
  59  		
  60  		/* read mine field, O(n2) */
  61  		for (i = 0; i < n; i++) {
  62  			scanf("%s\n",line);
  63  			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
  64  				inputField[i + MATRIX_OFFSET][j] = line[j - MATRIX_OFFSET];
  65  			}
  66  		}
  67  		
  68  		/* update output, O(n2) */ 
  69  		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
  70  			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
  71  				if (inputField[i][j] == MINE) {
  72  				
  73  					/* upper neighbours */
  74  					outputField[i-1][j-1]++;
  75  					outputField[i-1][j]++;
  76  					outputField[i-1][j+1]++;
  77  					
  78  					/* same level neighbours */
  79  					outputField[i][j-1]++;
  80  					outputField[i][j+1]++;
  81  					
  82  					/* lower neighbours */
  83  					outputField[i+1][j-1]++;
  84  					outputField[i+1][j]++;
  85  					outputField[i+1][j+1]++;
  86  				}
  87  			}
  88  		}
  89  		
  90  		/* present output, O(n2) */
  91  		printf("Field #%ld:\n",fieldNumber);
  92  		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
  93  			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
  94  				if (inputField[i][j] == MINE)
  95  					printf("%c", MINE);
  96  				else	
  97  					printf("%d",outputField[i][j]);
  98  			}
  99  			printf("\n");
 100  		}
 101  
 102  	}
 103  
 104      return 0;
 105  }