본문 바로가기

Studies/Programming Challenges (알고리즘 트레이닝 북)

문제 2. 지뢰 찾기 (Mine sweeper)

// Written by rinehart

// rinehart@naver.com

//2007. 6. 8

/* Note :  This code will be better if get map text from file. (I'm lazy...)

Maybe, some part of main function need to seperate to another functions */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAP_MAX 100
#define Type_New_map    1
#define Type_Read_map  2
#define Type_Exit               3


int Get_String(char *input_buf, int *m, int *n);


int Get_Result(char **map, char **result, int m, int n);


int Print_Result(char** result, int m, int n);


int Set_Mark(char* target);


int main()
{
        char buf[MAP_MAX];       
        char **map;
        char **result;
        int m = 0, n = 0, line_counter = -1;
        int Type = 0;
        int loop;

        while (1)
        {
                Type = Get_String(buf, &m, &n);

                if (Type == Type_Exit)
                        break;
                else if (Type == Type_New_map)
                {
                        map = malloc(sizeof(char*) * m);
                        result= malloc(sizeof(char*)*m);
                       
                        for (loop = 0; loop < m; loop++)
                        {
                                map[loop] = malloc(sizeof(int*)*n);
                                result[loop] = malloc(sizeof(char*)*n);
                        }
                               
                        line_counter = 0;
                }
               
                for (loop = 0; loop < n; loop++)
                {
                        Type = Get_String(buf, &m, &n);
                        if (line_counter >= m)
                        {
                                // Get the Result
                                m = 0;               
                        }
                        else
                        {
                                strcpy(map[line_counter], buf);
                                line_counter++;               
                        }
                }

                Get_Result(map, result, m, n);
                Print_Result(result, m, n);
        }
       
        printf ("\nEnd of Program\n");
       
        return 0;
}


int Get_String(char *a_buf, int *m, int *n)
{
        int result_Type = Type_New_map;
        int t_m, t_n;
        char *token;

        memset (a_buf, 0x00, sizeof(a_buf));
        gets(a_buf);

        if (a_buf[0] == '.' || a_buf[0] == '*')
        {
                result_Type = Type_Read_map;
        }
        else
        {
                token = strtok(a_buf, " \n");
                t_m = atoi(token);
                token = strtok(NULL, " \n");
                t_n = atoi(token);
                if(t_m ==0 && t_n == 0)
                        result_Type = Type_Exit;
                else
                {
                        *m = t_m;
                        *n = t_n;
                        result_Type = Type_New_map;
                }
        }

        return result_Type;
}


int Get_Result(char **map, char **result, int m, int n)
{
        int loop1, loop2;

        for (loop1 = 0; loop1 < m; loop1++)
        {
                for (loop2 = 0; loop2 < n; loop2++)
                {
                        result[loop1][loop2] = '0';
                }
        }

       
        for (loop1 = 0; loop1 < m; loop1++)
        {
                for (loop2 = 0; loop2 < n; loop2++)
                {
                        if (map[loop1][loop2] == '*')
                        {
                                result[loop1][loop2] = '*';

                                if (loop1 != 0)
                                {
                                        Set_Mark(&(result[loop1-1][loop2]));
                                        if (loop2 != 0)
                                                Set_Mark(&(result[loop1-1][loop2-1]));                                        
                                        if (loop2 != n-1)
                                                Set_Mark(&(result[loop1-1][loop2+1] ));
                                }
                                if (loop1 != m-1)
                                {
                                        result[loop1 +1][loop2] ++;
                                        if (loop2 != 0)
                                                Set_Mark(&(result[loop1 +1][loop2-1]));
                                        if (loop2 != n-1)
                                                Set_Mark(&(result[loop1 +1][loop2+1]));
                                }

                                if (loop2 != 0)
                                        Set_Mark(&(result[loop1][loop2-1]));                                   
                                if (loop2 != n-1)
                                        Set_Mark(&(result[loop1][loop2+1]));   
                        }
                }
        }

        return 0;
}


int Print_Result(char** result, int m, int n)
{
        int loop1, loop2;
        for (loop1 = 0; loop1 < m; loop1++)
        {
                for (loop2 = 0; loop2 < n; loop2++)
                {
                        printf ("%c", result[loop1][loop2]);
                }
                printf("\n");
        }
        printf("\n");

        return 0;
}


int Set_Mark(char* target)
{
        if (*target != '*')
                *target = *target+1;
        return 0;
}