/* * Programming Challeng: Minesweeper * PC/UVa IDs: 110102/10189 * * Attempt: 3 * Revision: 1 * * pfh - 09/19/06 * * Uses static arrays for better speed than attempt #1. Also, the improvement * over attempt 2 is that this doesn't use a separate array to count all the * bombs. * * First, it fills an array with '0' characters. When it finds a bomb in the * input array, it increments the surrounding respective locations in the * "counting" array. When it's done, it copies the bomb locations from the * input array into the counting array. This eliminates all the if's that * check the "upper-left, upper-right, etc". * * As it turns out, it's no faster, but because I simply increment all the * surrounding locations simultaneously everytime I find a bomb, my hope is to * use this when I study SIMD instructions. */#include <stdio.h>#include <string.h>#define MAX_COLUMS 1000#define MAX_ROWS 1000#define MAX_C (MAX_COLUMS+2) /* The parentheses are necessary so we */#define MAX_R (MAX_ROWS+2) /* don't mess up memset() later on. Also, * we need +2 because we don't do bounds * checking later on. */void solve_field( char f[MAX_R][MAX_C], int h, int w );intmain(){ int i; int w, h; /* The width and height of the current field */ int n; /* The current field number */ char p[MAX_R][MAX_C]; /* The current (unsolved) field */ n = 1; while( scanf("%d %d", &h, &w) == 2 ) { /* * A dimension of '0 0' is the flag to exit. */ if( (w == 0) && (h == 0) ) return 0; getchar(); for(i=1; i<=h; i++) { fread(p[i], 1, w, stdin); getchar(); } if( n > 1 ) printf("\n"); printf("Field #%d:\n", n); solve_field( p, h, w); ++n; } return 0;}/* * Solve a given field of '*' (bombs) and '.' (empty spaces) using standard * "Minesweeper" rules. */void solve_field( char f[MAX_R][MAX_C], int h, int w ){ int i, j; char nf[MAX_R][MAX_C]; memset(nf, '0', MAX_R*MAX_C);#define isbomb(y,x) (f[y][x] == '*')#define isclear(y,x) (f[y][x] == '.') /* Brute force method */ for( i=1; i <= h; i++ ) { for( j=1; j <= w; j++ ) { /* Are we on a bomb? */ if( isbomb(i,j) ) { nf[i-1][j-1]++; /* Upper left */ nf[i-1][j+1]++; /* Upper right */ nf[i+1][j-1]++; /* Lower left */ nf[i+1][j+1]++; /* Lower right */ nf[i-1][j]++; /* Above */ nf[i+1][j]++; /* Below */ nf[i][j-1]++; /* Left */ nf[i][j+1]++; /* Right */ } } } for( i=1; i <= h; i++ ) { for( j=1; j <= w; j++ ) if( isbomb(i,j) ) nf[i][j] = '*'; } for( i=1; i <= h; i++ ) { fwrite(nf[i]+1, 1, w, stdout); putchar('\n'); } }