Reverse Minesweeper

Question: The interviewer first discussed the game of minesweeper and the gave a reverse minesweeper problem where the specifications were as follows:
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:
inputoutput
4 4Field #1:
*...*100
....2210
.*..1*10
....1110
3 5Field #2:
**...**100
.....33200
.*...1*100
6 5Field #3:
.*.*.2*3*2
*.*.**3*3*
.....35453
**********
.*.*.3*5*3
.....11211
1 1Field #4:
.0
1 1Field #5:
**
2 2Field #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