[c언어] 순환 / 큰 값으로 만들어주는 길 찾기

m[0][0]에서 m[3][3]까지 가는데 합이 가장 큰 길은??

M배열에 자기 까지의 최고 합을 메모한다.

 

m배열

6	7	12	5
5	3	11	18
7	17	3	3
8	10	14	9

 

 #include <stdio.h>
#include <stdlib.h>
 
int matrixPath(int m[][4], int r, int c, int i, int j, int M[][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 (M[0][j] == 0)
            M[0][j] = matrixPath(m, r, c, 0, j - 1, M) + m[i][j];
        printf("M[%d][%d] :%d  \n", i, j, M[i][j]);
 
        return M[0][j];
 
    }
    else if (j == 0)
    {
        if (M[i][0] == 0)
            M[i][0] = matrixPath(m, r, c, i - 1, 0, M) + m[i][j];
        printf("M[%d][%d] :%d  \n", i, j, M[i][j]);
       
        return M[i][0];
 
    }
    else
    {
        int a, b;
        if (M[i - 1][j] == 0)
            M[i - 1][j] = matrixPath(m, r, c, i - 1, j, M);
        if (M[i][j - 1] == 0)
            M[i][j - 1] = matrixPath(m, r, c, i, j - 1, M);
        a = M[i - 1][j];
        b = M[i][j - 1];
        printf("M[%d][%d] :%d , M[%d][%d]: %d \n",i-1, j, a, i, j-1,b);
        return ((M[i - 1][j] < M[i][j - 1]) ? M[i - 1][j] : M[i][j - 1]) + m[i][j];
    }
}
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;
    //int **M ;
 
    int M[4][4];
    r = c = 4; // 4x4 matrix
 
   
    for(i = 0; i < r; i++)
        for (j = 0; j < c; j++)
        {
            M[i][j] = 0;
 
       
        }
       
 
 
        printf("%d\n", matrixPath(m, r, c, 3, 3, M));
}