저는 map[1~n][1~m] 에 정보를 저장하고 그것들 둘러 싼부분을 모두 -1로 처리했습니다.

사실 dp로 풀어보려고 했는데 dfs가 된 느낌이네요

dp의 파라미터인 curr_i, curr_j가 각각 n과 m에 도달하면 cnt++(전역변수, 초기화는 init함수에 했습니다.)해줌으로서 정답을 추가하게 했습니다. 

궁금한 점

1) 제 dp함수의 시간 복잡도는 최소 O(4^(n+m))라고 생각하는데 (물론 모든 노드를 방문했을 때) 이게 맞나요? (사실 계산하는 법을 전혀 모르겠네요 ㅠㅠ)

2) 23% 쯤에서 시간 초과가 나는데 제가 생각해본 이유로는

         1. 싸이클 - 근데 사실 내리막에 대한 정보 때문에 이 이유는 아닐것 같긴한데 일단 적어봅니다.

         2. 이게 dp를 신경쓰기보다 dfs를 생각하면서 풀었기 때문에 서로 다른 길이라도 겹치는 부분이 있다면 그 부분부터는 수행을 종료하고

            cnt값을 증가시켜주는 방식으로 풀어야 시간초과를 해결할 수 있지 않을가 생각햇습니다

                        => 하지만 이 방법을 사용하기에는 너무 복잡하네요ㅠㅠ 문제의 근본적인 틀을 바꾸는게 낫지 않을까 생각해서 질문 남겨봅니다

                           @.@ 저는 벌써 머리가 굳네요 

시간 초과를 위해 어떻게 해주는게 좋을까요?ㅠㅠ