运用动态规划

 

A点有一个过河卒，需要走到目标B点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制9个点（图中的 P1,P2⋯P8和C）。卒不能通过对方马的控制点。

棋盘用坐标表示，A点（0，0）、B点（n，m）、C 点（cx ​，cy ​）(0<cx<n≤20，0<cy<m≤20)。现在要求你计算出过河卒从A 点能够到达B 点的路径的条数。注：象棋中马走“日”。

输入格式

输入4个整数，n，m，cx ​，cy ​，分别表示B 点的横纵坐标和C 点的横纵坐标。

输出格式

输出一个整数，代表从A 点走到B 点的所有路径数。

样例输入

5 5 2 4

样例输出

14

import java.util.Scanner;
public class Main {

	/**
	 * @param args
	 */
	static int[][] map=new int[31][31];//马的控制点
	static long[][] f=new long[31][31];//计数
	static int n,m,cx,cy;//坐标
	static int[][] x={{1,2},{-1,2},{1,-2},{-1,-2},{2,-1},{2,1},{-2,1},{-2,-1}}; 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		n=in.nextInt();
		m=in.nextInt();
		cx=in.nextInt();
		cy=in.nextInt();
		for(int i=0;i<30;i++){
				for(int j=0;j<30;j++)
					map[i][j]=0;//将数组初始化为0
		}
			map[cx][cy]=1;//马控制点
			for(int i=0;i<8;i++){
				int tx=cx+x[i][0];//计算马控制点横坐标
				int ty=cy+x[i][1];//计算马控制点纵坐标
				if(tx>=0&&tx<=n&&ty>=0&&ty<=m)
					map[tx][ty]=1;
			}
			f[0][0]=1;
			for(int i=0;i<=n;i++){
				for(int j=0;j<=m;j++){
					 if(i!=0&&map[i][j]!=1)
						 f[i][j]=f[i][j]+f[i-1][j];
					 if(j!=0&&map[i][j]!=1)
						 f[i][j]=f[i][j]+f[i][j-1];
				}
			} 
			System.out.println(f[n][m]);
			 
		}
	}