#1504 : 骑士游历
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在8x8的国际象棋棋盘上给定一只骑士（俗称“马”）棋子的位置(R, C)，小Hi想知道从(R, C)开始移动N步一共有多少种不同的走法。
输入
第一行包含三个整数，N，R和C。
对于40%的数据， 1 <= N <= 1000000
对于100%的数据， 1 <= N <= 1000000000 1 <= R, C <= 8
输出
从(R, C)开始走N步有多少种不同的走法。由于答案可能非常大，你只需要输出答案模1000000007的余数。
样例输入
2 1 1
样例输出
12
一个通俗的想法：f[k][i][j]，第k步可以到达(i,j)的步法总数。
f[k+1][i][j]是在第k步的基础上走1步到达(i,j)的步法总数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| import java.util.Scanner;
public class Main {
static long[][][] data=new long[2][12][12];
static int[] dx=new int[]{-2,-2,-1,-1,1,1,2,2};
static int[] dy=new int[]{-1,1,-2,2,-2,2,-1,1};
static int pre=0,cur=0;
static int mod=1000000007;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int r=sc.nextInt();
int c=sc.nextInt();
data[0][r][c]=1;
pre=0;
cur=1;
for (int step = 1; step <= n; step++) {
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
data[cur][i][j]=0;
}
}
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
//八个方向
for (int f = 0; f < 8; f++) {
int x=i+dx[f];
int y=j+dy[f];
if(x>=1 && x<=8 && y>=1 && y<=8)
data[cur][x][y]=(data[cur][x][y]+data[pre][i][j])%mod;
}
}
}
pre=pre^1;
cur=cur^1;
}
long ans=0;
for (int i = 1; i <= 8; i++) {
for (int j = 1; j < 8; j++) {
ans=(ans+data[pre][i][j])%mod;
}
}
System.out.println(ans);
}
}
}
|