P1002 过河卒题解

樱花仙子 · 2020-02-22 00:34:25 · 个人记录

一、题意简述

给你一个二维棋盘和卒的起点为(0,0)。
求从起点A(0,0)绕过所在(mx,my)的马的攻击到终点B(bx,by)的所有线路。
二、题目分析

1. 题目描述分析
首先明确此题是线性动规(dp)，要求方案数。

此题还有一个关键元素：马，卒需要绕过马的攻击，但是马不会动。

2. 样例分析

1 0 0 0 0 0 0
0 0 -1 0 -1 0 0
0 -1 0 0 0 -1 0
0 0 0 -1 0 0 0
0 -1 0 0 0 -1 0
0 0 -1 0 -1 0 0
0 0 0 0 0 0 2

卒在(0,0)，用1表示，要到(6,6),用2表示。
马在(3,3)，卒没法走的地方用-1表示。

通往各点的方案数如图所示：

1 1 1 1 1 1 1
1 2 0 1 0 1 2
1 0 0 1 1 0 2
1 1 1 0 1 1 3
1 0 1 1 2 0 3
1 1 0 1 0 0 3
1 2 2 3 3 3 6

所以答案是6。

3.总体分析

题中有几个要解决的分问题：

处理马拦卒的问题。
用dp解决主问题求方案。

（一）马拦卒

先说一下，我习惯数组下标从1开始，所以都读入都+1了。

    bx++;by++;mx++;my++;

众所周知，马走“日”，一共就8个点，直接一套顺序结构不就行啦！

void mm(int i,int j){
    a[i][j]=-1;
    a[i-2][j-1]=-1;
    a[i-2][j+1]=-1;
    a[i-1][j-2]=-1;
    a[i-1][j+2]=-1;
    a[i+1][j-2]=-1;
    a[i+1][j+2]=-1;
    a[i+2][j-1]=-1;
    a[i+2][j+1]=-1;
}

~~简单，提交。~~

成功RE ???

原来如果马的坐标带有1，数组就会尝试访问负数的数组下标，导致RE。

所以我们只能用循环结构配合if语句啦！

void mm(int i,int j){
    a[i][j]=-1;
    for(int k=1;k<=8;k++){
        int x=i+di[k];
        int y=j+dj[k];
        if(x>0&&x<=bx&&y>0&&y<=by)a[x][y]=-1;
    }
}

（二）计算方案数

先把上面那个图拉下来

1 1 1 1 1 1 1
1 2 0 1 0 1 2
1 0 0 1 1 0 2
1 1 1 0 1 1 3
1 0 1 1 2 0 3
1 1 0 1 0 0 3
1 2 2 3 3 3 6

状态：我们设f[i][j]表示从卒(0,0)到绕过马到a[i][j]的总方案数。
状态转移方程：观察上面的图片，可以发现：

f[i][j]=f[i-1][j]+f[i][j-1]

再根据题目中过河卒，从左上向右下走，所以卒只能向右或者向下走，所以当前状态只能从上面或左边来，更能验证这个状态转移方程。

但这个方程不能直接使用，f[1][1]无法得到值,所以只能改变一下方程。

f[i][j]=max(f[i][j],f[i-1][j]+f[i][j-1]

初值：显然所有答案便是从开始位置(0,0)出来的,给(0,0)赋初值就是f[1][1]=1。
马拦卒：既然不能走，那就直接等于0（相当于不做跳过这个状态）。

三、代码

#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int di[9]={0,-2,-1,1,2,-2,-1,1,2};
int dj[9]={0,-1,-2,-2,-1,1,2,2,1};
unsigned long long f[105][105];
long long mx,my,bx,by;
template<class T>void read(T &x)//快读
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return;
}
inline void write(int n)//快输
{
    if(n<0){
        putchar('-');
        n=0-n;
    }
    if(n>=10){
        write(n/10);
    }
    putchar((n%10)+'0');
    return;
}
void mm(int i,int j){//判断马的落点
    a[i][j]=-1;
    for(int k=1;k<=8;k++){
        int x=i+di[k];
        int y=j+dj[k];
        if(x>0&&x<=bx&&y>0&&y<=by)a[x][y]=-1;                                 //避免数组越界
    }
}
void print(long long a[][105],int m,int n){
    for(int i=1;i<=m;i++){
        for(int j=1;j<n;j++){
            cout<<a[i][j]<<"  ";
        }
        cout<<a[i][n]<<endl;
    }
}//输出（用于测试）
int main(){
    f[1][1]=1;//初值
    read(bx);read(by);read(mx);read(my);
    bx++;by++;mx++;my++; 
    mm(mx,my);
    for(int j=1;j<=by;j++)//动态规划部分
        for(int i=1;i<=bx;i++){
            if(a[i][j]==-1)continue;
                   //若有马，不执行
            f[i][j]=max(f[i][j],f[i-1][j]+f[i][j-1]);//转移方程
        }
    cout<<f[bx][by];//输出答案
    return 0;
}

四、执行分析

1.时间复杂度：

双重循环：复杂度为O(bxby)。题中时限为 1sec，大约为10亿次计算，bx与by最大为20。

## 2.空间复杂度：数组只要开到$25^2$，很保险了，$bxby$最大才为20。内存限制125MB，差不多30 000 000 个int，25$^2$为625个int，也远小于，不会超空间。

P1002 过河卒 题解