1. A block of M rows by N columns is given
2. Each item can either be a mine or not a mine
3. The location of the mines in the block is given by the character *
4. Normal/safe squares are marked by '.' (dots)
See the below table and write a program to print the number of mines adjacent to the safe blocks.
Update: This problem is from the book "Programming Challenges - The Programming Contest Training Manual - Skiena".
Example:
input | output |
4 4 | Field #1: |
*... | *100 |
.... | 2210 |
.*.. | 1*10 |
.... | 1110 |
3 5 | Field #2: |
**... | **100 |
..... | 33200 |
.*... | 1*100 |
6 5 | Field #3: |
.*.*. | 2*3*2 |
*.*.* | *3*3* |
..... | 35453 |
***** | ***** |
.*.*. | 3*5*3 |
..... | 11211 |
1 1 | Field #4: |
. | 0 |
1 1 | Field #5: |
* | * |
2 2 | Field #6: |
*. | *2 |
.* | 2* |
0 0 |
Program:
#include <stdio.h> #include <malloc.h> #define MINE -1 void Read_Arrays(); void FillNumbers(int * array, int rows, int cols); void UpdateNeighbors(int *array, int row_index, int col_index, int max_row, int max_col); void print_array(int *array, int rows, int cols); int get_val(int *array, int row_index, int col_index, int cols); // increment the value at the specified array location int inc_val(int *array, int row_index, int col_index, int cols); int main(void) { Read_Arrays(); } void Read_Arrays() { int rows = 0; int cols = 0; int cur_row_index; int *array; char line[256]; int field_num = 0; while(fgets(line, 256, stdin) != NULL) { int i=0; if(rows == 0 && cols == 0) { sscanf(line, "%d %d", &rows, &cols); array = (int *)malloc(rows*cols*sizeof(int)); if(array == NULL) { printf("failed to allocate memory\n"); return; } if(rows == 0 || cols == 0) { return; } cur_row_index = 0; continue; } for(i= 0; i<cols; i++) { char c = line[i]; if(c == '*') c = MINE; else c = 0; *(array + (cur_row_index*cols)+i) = c; } //if we scanned the specified number of rows lets process the array if(cur_row_index == rows - 1) { FillNumbers(array, rows, cols); printf("Field #%d:\n", ++field_num); print_array(array, rows, cols); free(array); rows = 0; cols = 0; } else { cur_row_index++; } } } /* fill numbers in the array instead of dots */ void FillNumbers(int *array, int rows, int cols) { int i, j; for(i=0; i<rows; i++) { for(j=0; j < cols; j++) { if(*(array + (i*cols) + j) == MINE) { UpdateNeighbors(array, i, j, rows, cols); } } } } /* this function will increment mine count for the neighbors of the mine */ void UpdateNeighbors(int *array, int row_index, int col_index, int max_row, int max_col) { if(row_index-1 >= 0) { if(col_index - 1 >= 0) inc_val(array, row_index - 1, col_index -1, max_col); inc_val(array, row_index -1, col_index, max_col); if(col_index + 1 < max_col) inc_val(array, row_index -1, col_index + 1, max_col); } if(col_index - 1 >= 0) inc_val(array, row_index, col_index - 1, max_col); if(col_index + 1 < max_col) inc_val(array, row_index, col_index + 1, max_col); if(row_index + 1 < max_row) { if(col_index - 1 >= 0) inc_val(array, row_index + 1, col_index -1, max_col); inc_val(array, row_index + 1, col_index, max_col); if(col_index + 1 < max_col) inc_val(array, row_index + 1, col_index+1, max_col); } } int get_val(int *array, int row_index, int col_index, int cols) { return *(array + (row_index * cols) + col_index); } /* we increment only if there is no mine present at the specified location */ int inc_val(int *array, int row_index, int col_index, int cols) { int val = get_val(array, row_index, col_index, cols); if(val == MINE) return; *(array + (row_index * cols) + col_index) += 1; } void print_array(int *array, int rows, int cols) { int i, j; for(i = 0; i < rows; i++) { for(j = 0; j < cols; j++) { int val = get_val(array, i, j, cols); if(val != MINE) printf("%d", val); else printf("%c", '*'); } printf("\n"); } }
No comments:
Post a Comment