산길 내려가는 경로찾기

http://hancom.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=1024&sk=&sv=&menu=&sst=qs_code&sod=asc&page=10&fv=1

 

문제는 위 주소입니다.

문제 보자마자 재귀가 생각나서 허접하게 짜봤는데요..

이게 재귀를 너무 많이 해서 그런지 10개중에 2개가 시간초과가 뜨더라구요.. ㅠㅠ

다른방법으로 풀려고 해봤는데 이 방법 말고는 딱히 떠오르는 것도 없고 해서..

작동 시간 줄이는 방법 없을까요?

#include <stdio.h> 

int road[500][500]={0,};

int counts[500][500]={0,}; 

int m,n; 

void Down(int x, int y) {  

    int i, j, k;

    for(k=0;k<m;k+=1) {

        counts[0][0]=1;

        for(i=0; i<m;i+=1) { 

            for(j=0; j<n; j+=1) {

                if(i>0 || j>0) counts[i][j]=0;

                if(i-1>-1 && road[i-1][j]>road[i][j]) { counts[i][j]+=counts[i-1][j]; }

                if(i+1<m && road[i+1][j]>road[i][j]) { counts[i][j]+=counts[i+1][j]; }

                if(j-1>-1 && road[i][j-1]>road[i][j]) { counts[i][j]+=counts[i][j-1]; }

                if(j+1<n && road[i][j+1]>road[i][j]) { counts[i][j]+=counts[i][j+1]; }

           }

        } 

    }

} 

int main() {  

   //freopen("input.txt","r",stdin); 

   //freopen("output.txt","w",stdout); 

    int i, j, k; 

    //m=500;

    //n=500;

    scanf("%d %d",&m,&n); 

    //k=m*n+10;

    for(i=0; i<m;i+=1) { 

        for(j=0; j<n; j+=1)

            scanf("%d", &road[i][j]); 

    } 

    Down(0,0); 

    printf("%d\n", counts[m-1][n-1]); 

    return 0; 

}