package bj.gold.l4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* @author 은서파
* @since 2021. 9. 23.
* @see https://www.acmicpc.net/problem/1520
* @perf 38916 348
* @category #DP, #DFS
* @고려사항
* overlapping subproblem이면서 optimize substructure이기 때문에 DP를 이용해서 풀어줘야 한다.
* memo[i][j] = i, j에서 목적지인 (R-1, C-1)에 도착하는 경우의 수
* 이때 memo를 이용한 방문 체크 시 초기값을 -1로 잡아주고 방문하면 0으로 일단 초기화 후 탐색 회수를 업데이트 해준다.
*/
public class BJ_G4_1520_내리막길 {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder output = new StringBuilder();
static StringTokenizer tokens;
static int R, C;
static int [][] map;
// memo[r][c] = map[r][c]에서 map[R-1][C-1]에 도달하는 경우의 수
static int [][] memo;
static int [][] deltas = {{-1, 0},{1, 0},{0, -1},{0, 1}};
public static void main(String[] args) throws IOException {
input = new BufferedReader(new StringReader(src));
tokens = new StringTokenizer(input.readLine());
R = Integer.parseInt(tokens.nextToken());
C = Integer.parseInt(tokens.nextToken());
map = new int [R][C];
for(int r=0; r<R; r++) {
tokens = new StringTokenizer(input.readLine());
for(int c=0; c<C; c++) {
map[r][c] = Integer.parseInt(tokens.nextToken());
}
}// 입력 완료!!
memo = new int [R][C];
// 배열의 초기값은 0 --> 길이 없는건지(0), 아니면 안가본건지 알수가 없다.
for(int [] row: memo) {
Arrays.fill(row, -1);
}
// 일종의 기저조건
memo[R-1][C-1]=1;
// 0, 0에서 사방탐색으로 출발해서 답을 찾아보자.
int answer = find(0, 0);
System.out.println(answer);
}
private static int find(int r, int c) {
//memo 활용
if(memo[r][c]!=-1) {
return memo[r][c];
}
// -1이라면 처음 방문한 경우 - 현재 지점을 0으로 초기화 하고 자식 탐색 --> memo에 결과 업데이트
memo[r][c]=0;
for(int d=0; d<deltas.length; d++) {
int nr = r + deltas[d][0];
int nc = c + deltas[d][1];
// 범위 안에 있고.. 내리막길이라면 가보자!! , 일반적인 4방 탐색에서는 visited 배열을 이용해서 왔던길 안가도록 처리 필요
// 여기서는 무조건 내리막으로만 이동 --> 따라서 왔던 길을 다시 가는 불상사는 발생할 리가 없다.
if(isIn(nr, nc) && map[r][c]>map[nr][nc]) {
memo[r][c]+=find(nr, nc);
}
}
return memo[r][c];
}
private static boolean isIn(int r, int c) {
return 0<=r && r<R && 0<=c && c<C;
}
// REMOVE_START
private static String src = "4 5\r\n" +
"50 45 37 32 30\r\n" +
"35 50 40 20 25\r\n" +
"30 30 25 17 28\r\n" +
"27 24 22 15 10";
// REMOVE_END
}