[c언어] 미로 길 찾기

미로 길 찾기

 

 

#include <stdio.h>
#include <stdlib.h>
 
int matrixPath(int **m, int r, int c, int i, int j, int **M, int **N)
{
    if (i == 0 && j == 0)
        return m[i][j];
   
    else if (i == 0)
    {
        if (N[0][j] == 0)
        {
            M[0][j] = matrixPath(m, r, c, 0, j - 1, M, N) + m[i][j];
            N[0][j] = 1;
        }
        return M[0][j];
    }
    else if (j == 0)
    {
        if (N[i][0] == 0)
        {
            M[i][0] = matrixPath(m, r, c, i - 1, 0, M, N) + m[i][j];
            N[i][0] = 1;
 
        }
        return M[i][0];
    }
    else
    {
        int a, b;
        if (N[i - 1][j] == 0)
        {
            M[i - 1][j] = matrixPath(m, r, c, i - 1, j, M, N);
            N[i - 1][j] = 1;
        }
        if (N[i][j - 1] == 0)
        {
            M[i][j - 1] = matrixPath(m, r, c, i, j - 1, M, N);
            N[i][j - 1] = 1;
        }
        a = M[i - 1][j];
        b = M[i][j - 1];
        return ((a < b) ? a : b) + m[i][j];
    }
}
int main(void)
{
 
    int i, j, r, c;
    int **M;
    int **N;
    int **m;
    printf("enter row and column\n");
    printf("number of row:");
    scanf("%d", &r);
    printf("number of column:");
    scanf("%d", &c);
    m = (int**)malloc(sizeof(int*) * r);
    M = (int**)malloc(sizeof(int*) * r);
    N = (int**)malloc(sizeof(int*) * r);
    for (i = 0; i < r; i++)
    {
        m[i] = (int*)malloc(sizeof(int) * c);
        M[i] = (int*)malloc(sizeof(int) * c);
        N[i] = (int*)malloc(sizeof(int) * c);
    }
   
    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
        {
            M[i][j] = 0;
            N[i][j] = 0;
        }
    printf("%d x %d 행렬의 값을 입력하세요:\n", r, c);
   
    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
            scanf("%d", &m[i][j]);
 
    printf("%d\n", matrixPath(m, r, c, r - 1, c - 1, M, N));
    for (i = 0; i < r; i++)
    {
        free(m[i]);
        free(M[i]);
        free(N[i]);
    }
 
    free(m);
    free(M);
    free(N);
}

 

#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
 
int matrixPath(int m[][4], int r, int c, int i, int j, int M[][4], bool check[][4]);
int main(void)
{
   
    int m[4][4] = { { 6,7,12,5 },{ 5,3,11,18 },{ 7,17,3,3 },{ 8,10,14,9 } };
    int i, j, r, c;
    bool check[4][4] = { false };
 
    int M[4][4] = {0};
    r = c = 4;
   
    printf("%d\n", matrixPath(m, r, c, 3, 3, M, check));
}
int matrixPath(int m[][4], int r, int c, int i, int j, int M[][4], bool check[][4])
{
    if (i == 0 && j == 0)
    {
        printf("m[%d][%d] :%d  \n", i, j, m[i][j]);
        return m[i][j];
    }
    else if (i == 0)
    {
        if (!check[0][j])
        {
 
            M[0][j] = matrixPath(m, r, c, 0, j - 1, M, check) + m[i][j];
            check[0][j] = true;
        }
        printf("M[%d][%d] :%d  \n", i, j, M[i][j]);
 
        return M[0][j];
 
    }
    else if (j == 0)
    {
        if (!check[i][0])
        {
 
 
            M[i][0] = matrixPath(m, r, c, i - 1, 0, M, check) + m[i][j];
 
            check[i][0] = true;
        }
        printf("M[%d][%d] :%d  \n", i, j, M[i][j]);
 
        return M[i][0];
 
    }
    else
    {
        int a, b;
        if (!check[i - 1][j])
        {
            M[i - 1][j] = matrixPath(m, r, c, i - 1, j, M, check);
            check[i - 1][j] = true;
        }
        if (!check[i][j - 1])
        {
            M[i][j - 1] = matrixPath(m, r, c, i, j - 1, M, check);
            check[i][j - 1] = true;
        }
    
 
        return ((M[i - 1][j] < M[i][j - 1]) ? M[i - 1][j] : M[i][j - 1]) + m[i][j];
    }
}