1520.txt

package block;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main
{
	static int map[][] = new int[501][501];
	static int dp[][] = new int[501][501];
	static int dx[] = { 0, -1, 0, 1 };
	static int dy[] = { -1, 0, 1, 0 };
	static int M, N;
	
	static final int NONE = -1;
	
	static
	{
		for (int i = 1; i < 501; i++)
		{
			Arrays.fill(dp[i], NONE);
		}
	}
	
	static int check(int i, int j)
	{
		if (i == M && j == N)
			return 1;
		if (dp[i][j] > NONE)
			return dp[i][j];
		
		int ret = 0;
		
		for (int k = 0; k < 4; k++)
		{
			int nx = i + dx[k];
			int ny = j + dy[k];
			if (1 > nx || nx > M || 1 > ny || ny > N)
				continue;
			if (map[nx][ny] < map[i][j])
				ret += check(nx, ny);
		}
		return dp[i][j] = ret;
	}
	
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		for (int i = 1; i <= M; i++)
		{
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++)
			{
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		System.out.println(check(1, 1));
		// for (int i = 1; i <= M; i++)
		// {
		// for (int j = 1; j <= N; j++)
		// {
		// System.out.print(dp[i][j] + " ");
		// }
		// System.out.println();
		// }
	}
}