DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

A Solution For The Minesweeper Problem

03.08.2008
| 14162 views |
  • submit to reddit
        A solution for the Minesweeper problem.
 
Problem description:
<a href="http://icpcres.ecs.baylor.edu/onlinejudge/external/101/10189.html">http://icpcres.ecs.baylor.edu/onlinejudge/external/101/10189.html</a>

Author: <a href="http://joanatrindade.wikidot.com">Joana Matos Fonseca da Trindade</a>
Date: 2008.03.08

/* 
 * A solution for the Minesweeper problem.
 * UVa ID: 10189
 */
#include <stdio.h>

#define MINE '*'
#define MATRIX_OFFSET 1

int main (int argc, const char * argv[]) {
	/* number of lines of the mine field */
	long n;
	
	/* number of colums of the mine field */
	long m;
	
	/* iterators for retrieving the content of each field line*/
	long i, j;
	
	/* field number identifier */
	long fieldNumber = 0;

	while(scanf("%ld %ld", &n, &m) != EOF) {
			
		/* 0 0, ends the program */
		if (!n && !m) {
			return 0;
		} else {
			if (fieldNumber > 0) {
				/* 
				 * workaround for the extra line on the output, 
				 * which was giving me a Wrong Answer verdict..
				 * so only insert an extra line if there's more
				 * to come :-) 
				 */
				printf("\n");
			}
		}
		
		/* increment field id */
		fieldNumber++;
				
		/* a bidimensional array representing the input mine field */
		char inputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
		
		/* a bidimensional array to output the mine field */
		int outputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
		
		/* temporary variable to retrieve mine field lines */
		char line[m];
		
		/* init, O(n2) */
		for (i = 0; i < n + MATRIX_OFFSET + 1; i++) {
			for (j = 0; j < m + MATRIX_OFFSET + 1; j++) {
				outputField[i][j] = 0;
			}
		}
		
		/* read mine field, O(n2) */
		for (i = 0; i < n; i++) {
			scanf("%s\n",line);
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				inputField[i + MATRIX_OFFSET][j] = line[j - MATRIX_OFFSET];
			}
		}
		
		/* update output, O(n2) */ 
		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				if (inputField[i][j] == MINE) {
				
					/* upper neighbours */
					outputField[i-1][j-1]++;
					outputField[i-1][j]++;
					outputField[i-1][j+1]++;
					
					/* same level neighbours */
					outputField[i][j-1]++;
					outputField[i][j+1]++;
					
					/* lower neighbours */
					outputField[i+1][j-1]++;
					outputField[i+1][j]++;
					outputField[i+1][j+1]++;
				}
			}
		}
		
		/* present output, O(n2) */
		printf("Field #%ld:\n",fieldNumber);
		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				if (inputField[i][j] == MINE)
					printf("%c", MINE);
				else	
					printf("%d",outputField[i][j]);
			}
			printf("\n");
		}

	}

    return 0;
}
    

Comments

Snippets Manager replied on Sun, 2009/01/18 - 1:25am

Thanks for sharingI found it very readable and learned a lot from your code. One question: what is the constant MATRIX_OFFSET used for? ie) why did you include it, how is it useful?