计蒜客:马踏过河卒 (java)

运用动态规划

计蒜客:马踏过河卒 (java)

 

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]);
			 
		}
	}

上一篇:31-集群的相关概念


下一篇:第二阶段31--泛型_泛型方法_泛型方法与可变参数