내리막길

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Exam1520 {

static int N, M;

static int D[][], grid[][];

public static void main(String[] args) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());

M = Integer.parseInt(st.nextToken());

grid = new int[N + 1][M + 1];

D = new int[N + 1][M + 1];

for (int i = 1; i <= N; i++) {

st = new StringTokenizer(br.readLine());

for (int j = 1; j <= M; j++) {

int a = Integer.parseInt(st.nextToken());

grid[i][j] = a;

}

}

for(int i=1;i<=N;i++)

for(int j=1;j<=M;j++)

D[i][j] = -1;

goGrid(1, 1);

System.out.println(D[1][1]);

}

static int goGrid(int x, int y) {

if (D[x][y]!=-1)

return D[x][y];

if (x == N && y == M)

return 1;

D[x][y] = 0;

if (y != M && grid[x][y + 1] < grid[x][y])

D[x][y] += goGrid(x, y + 1);

if (x != 1 && grid[x - 1][y] < grid[x][y])

D[x][y] += goGrid(x - 1, y);

if (y != 1 && grid[x][y - 1] < grid[x][y])

D[x][y] += goGrid(x, y - 1);

if (x != N && grid[x + 1][y] < grid[x][y])

D[x][y] += goGrid(x + 1, y);

return D[x][y];

}

}