前言
无论国际象棋还是中国象棋中，马的走位都是先横着或直着走一格，然后再斜着走一个对角线，俗称“马走日”。
那么在一个特定棋盘中马在有限步数下有多少种走法？今天就研究一个关于“马走日”的问题：骑士游历。
国际象棋
题目
时间限制: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
分析
首先，比较直观的思路是严格按照规则，每走一步记录状态，每个状态下马走的路径最多8条，然后迭代查询每条下面路径下的子路径，最后求的结果。这种思路是指数型增长的，并且迭代调用函数，可能没计算几步计算机就无能为力了。
既然迭代不行，就可以用动态规划，记录每一点每一步状态下可能的路径，但是这个方法在 N = 1000000000的时候还是会超时。
因为N会很大，如果按照直观思路肯定是无法解，要么找到循环规律之类，要们降低N计算次数。
对于本题，我们看到其实马走的路径彼此之间是唯一联系的，可以看作是连通图，然后连通图的邻接矩阵A乘法就是路径状态的记录。比如在8x8对于点（1，1），初始状态与他相连的点是（2，3），（3，2），邻接矩阵（1，1）对应的行状态就是[0,0,...,1(10),0,..0...1(17),0]，所以如果N=1，总路径就是2。N=2，我们就需要进行矩阵乘法AxA，（1，1）对应的状态会变成[2,0,1,0,1,0...0,1(11)，0...0,1(16),0..0,1(20),0...0,1(25),0,2,0..0,1(32),0,1,0...0]，总路径就是12。
初始联通图：
void initGrid()
{
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
int index = (i-1)*8+j-1;
if (j + 2 <= 8 && i + 1 <= 8) {
int temp = i*8+j+1;
grid[index][temp] = 1;
}
if (j + 1 <= 8 && i + 2 <= 8) {
int temp = (i+1)*8+j;
grid[index][temp] = 1;
}
if (j + 2 <= 8 && i - 1 >= 1) {
int temp = (i-2)*8+j+1;
grid[index][temp] = 1;
}
if (j + 1 <= 8 && i - 2 >= 1) {
int temp = (i-3)*8+j;
grid[index][temp] = 1;
}
if (j - 1 >= 1 && i - 2 >= 1) {
int temp = (i-3)*8+j-2;
grid[index][temp] = 1;
}
if (j - 2 >= 1 && i - 1 >= 1) {
int temp = (i-2)*8+j-3;
grid[index][temp] = 1;
}
if (j - 1 >= 1 && i + 2 <= 8) {
int temp = (i+1)*8+j-2;
grid[index][temp] = 1;
}
if (j - 2 >= 1 && i + 1 <= 8) {
int temp = i*8+j-3;
grid[index][temp] = 1;
}
}
}
}
有了上面的原理，我们求某点出发的路径总数，只需要进行矩阵乘法就行了，但是N很大，如果直接计算还是不行，我们需要用到快速幂运算。其原理就是把指数看作二进制数，比如A5，5看作二进制数就是101，A5=A1x22xA0x21xA1x20，一个数记录a=A2x，另一个数记录结果res，遇到二进制数为1就res=resxa，计算次数降低到log2N。快速幂运算不仅适用于数字，矩阵其实也是一样的。只是乘积算法不同，对于数字，res初始为1，矩阵初始就是Indentity Martrix。
void mul1() // res * grid
{
long long temp[64][64];
memset(temp, 0, sizeof(temp));
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
for (int k = 0; k < 64; k++) {
temp[i][j] += res[i][k] * grid[k][j];
temp[i][j] %= m;
}
}
}
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
res[i][j] = temp[i][j];
}
}
}
void mul2() // grid * grid
{
long long temp[64][64];
memset(temp, 0, sizeof(temp));
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
for (int k = 0; k < 64; k++) {
temp[i][j] += grid[i][k] * grid[k][j];
temp[i][j] %= m;
}
}
}
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
grid[i][j] = temp[i][j];
}
}
}
void Factor(long long n)
{
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
if (i == j) {
res[i][j] = 1;
}
else
{
res[i][j] = 0;
}
}
}
while (n) {
if (n&1) {
mul1();
}
mul2();
n>>=1;
}
}
结果
顺利AC，但是效率还有提高的地方。
完整代码：
//
// main.cpp
// 骑士游历
//
// Created by Jiao Liu on 7/9/19.
// Copyright © 2019 ChangHong. All rights reserved.
//
#include <iostream>
#include <string.h>
using namespace std;
long long grid[64][64];
long long res[64][64];
long long m = 1000000007;
long long n,r,c;
void initGrid()
{
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
int index = (i-1)*8+j-1;
if (j + 2 <= 8 && i + 1 <= 8) {
int temp = i*8+j+1;
grid[index][temp] = 1;
}
if (j + 1 <= 8 && i + 2 <= 8) {
int temp = (i+1)*8+j;
grid[index][temp] = 1;
}
if (j + 2 <= 8 && i - 1 >= 1) {
int temp = (i-2)*8+j+1;
grid[index][temp] = 1;
}
if (j + 1 <= 8 && i - 2 >= 1) {
int temp = (i-3)*8+j;
grid[index][temp] = 1;
}
if (j - 1 >= 1 && i - 2 >= 1) {
int temp = (i-3)*8+j-2;
grid[index][temp] = 1;
}
if (j - 2 >= 1 && i - 1 >= 1) {
int temp = (i-2)*8+j-3;
grid[index][temp] = 1;
}
if (j - 1 >= 1 && i + 2 <= 8) {
int temp = (i+1)*8+j-2;
grid[index][temp] = 1;
}
if (j - 2 >= 1 && i + 1 <= 8) {
int temp = i*8+j-3;
grid[index][temp] = 1;
}
}
}
}
void mul1() // res * grid
{
long long temp[64][64];
memset(temp, 0, sizeof(temp));
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
for (int k = 0; k < 64; k++) {
temp[i][j] += res[i][k] * grid[k][j];
temp[i][j] %= m;
}
}
}
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
res[i][j] = temp[i][j];
}
}
}
void mul2() // grid * grid
{
long long temp[64][64];
memset(temp, 0, sizeof(temp));
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
for (int k = 0; k < 64; k++) {
temp[i][j] += grid[i][k] * grid[k][j];
temp[i][j] %= m;
}
}
}
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
grid[i][j] = temp[i][j];
}
}
}
void Factor(long long n)
{
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
if (i == j) {
res[i][j] = 1;
}
else
{
res[i][j] = 0;
}
}
}
while (n) {
if (n&1) {
mul1();
}
mul2();
n>>=1;
}
}
int main(int argc, const char * argv[]) {
memset(grid, 0, sizeof(grid));
initGrid();
cin>>n>>r>>c;
Factor(n);
long long ans = 0;
long long index = (r-1)*8+c-1;
for (int i = 0; i < 64; i++) {
ans += res[index][i];
ans %= m;
}
cout<<ans<<endl;
return 0;
}
网友评论