东北小蟹蟹

[luogu p1002] 过河卒
题面传送门题目描述棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上C点有一...
扫描右侧二维码阅读全文
22
2019/09

[luogu p1002] 过河卒

题面

传送门
题目描述

棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示,A点(0,0)、B点(n,m)(n,m为不超过20的整数),同样马的位置坐标是需要给出的。
现在要求你计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

输入格式

一行四个数据,分别表示B点坐标和马的坐标。

输出格式

一个数据,表示所有的路径条数。

输入输出样例

输入 #1
6 6 3 3
输出 #1
6

说明/提示

结果可能很大!
------------------------------------------------

浅谈

本蒟蒻不会下任何棋,愣是没看懂题面qwq,看了题解才知道这道题是啥意思……
ps:马走日,我还真不知道:)

第一印象:m=20,n=20',再加上难度pj-` 哇?搜索!!!
然而转念一想,结果可能很大……
搜索一定会爆,这题得用dp

不过这既然是一道2002 pjdp应该不会很难。
嗯……

First Level

分析

好继续我们来胡乱正经分析一下
题目的大意就是求一个点到另一点的方法数,但其中有一些点不能走。(这得懂下棋常识,才能知道哪些点不等走啊qwq

比如说样例就是下面这个图(N表示不能走的格):

  0 1 2 3 4 5 6---横坐标序号
0 A 0 0 0 0 0 0
1 0 0 N 0 N 0 0
2 0 N 0 0 0 N 0
3 0 0 0 C 0 0 0
4 0 N 0 0 0 N 0
5 0 0 N 0 N 0 0
6 0 0 0 0 0 0 0
|-纵坐标序号(与图无关)

这图太单调太无趣了。我们挥动金手指魔改一下此图:

  0 1 2 3 4 5 6---横坐标序号
0 A 1 1 1 1 1 1
1 1 2 0 1 0 1 2
2 1 0 0 1 1 0 2
3 1 1 1 0 1 1 3
4 1 0 1 1 2 0 3
5 1 1 0 1 0 0 3
6 1 2 2 3 3 3 6(B)
|-纵坐标序号(与图无关)

我们把这个图定义为dp[i][j],其中dp[i][j]指的是A到`(i,j)点的路径数量。
我们可以轻松得出

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

explanation:
如果这是一个普通点,那么到达这个点的路径数自然为上一个的路径数+左一个的路径数。
毕竟……你想到达一个点,只能从上面那个点往下或左边那个点往右,路径数自然是他们的和。

但是鱿鱼在边界处用此转移方程会爆炸,所以我们要把整体所有的坐标都+1.
Like this:

  0 1 2 3 4 5 6 7---横坐标序号
0 0 0 0 0 0 0 0 0 
1 0 A 1 1 1 1 1 1
2 0 1 2 0 1 0 1 2
3 0 1 0 0 1 1 0 2
4 0 1 1 1 0 1 1 3
5 0 1 0 1 1 2 0 3
6 0 1 1 0 1 0 0 3
7 0 1 2 2 3 3 3 6(B)
|-纵坐标序号(与图无关)

其实相当于在上面和左面镶上了一道金边。但是初始值设在那里呢?直接在dp[1][1]吗?还是看这个方程:

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

自然,这个方程我们应该从i=1,j=1遍历。那么,dp[1][1]的值自然会更新成dp[0][1]+dp[1][0]=0+0=0,设了dp[1][1]=1却被更新了……:)
所以我们应该从金边下手。观察如上方程得知dp[1][1]的值与dp[0][1]dp[1][0]有关,从他们俩下手,那自然是极好的。
ok,我们设dp[0][1]=1吧。这样就得到了完整方程:

dp[0][1] = 1,
dp[Ni][Nj] = 0,
dp[i][j] = dp[i-1][j]+dp[i][j-1]

explanation:
Ni,Nj为马及马的控制点

程序

既然dp方程写好啦,那就开始程序吧!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;//头文件和命名空间
int bx,by,cx,cy;//b,c的坐标
unsigned long long dp[25][25];//注意结果很大,得开ull哦。
bool f[25][25];//看是否为马的控制点
const int fx[9]={0,-2,-1,1,2,2,1,-1,-2};
const int fy[9]={0,1,2,2,1,-1,-2,-2,-1};
//看到后面你就知道这是啥了
int main()
{
    scanf("%d%d%d%d",&bx,&by,&cx,&cy);//输入
    bx++;by++;cx++;cy++;dp[0][1]=1;//加1防越界,设置dp初值
    for(int i=0;i<9;i++)
        f[cx+fx[i]][cy+fy[i]]=true;//懒人福利~~
    for(int i=1;i<=bx;i++)
        for(int j=1;j<=by;j++)
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])*(!f[i][j]);//计算dp的值。如果是马(的控制点),自然是0啦
    /*
    for(int i=1;i<=bx;i++)
    {
        for(int j=1;j<=by;j++)
            printf("%12lld",dp[i][j]);
        printf("\n");
    }
    测试输出
    */
    printf("%lld\n",dp[bx][by]);//输出
    return 0;
}

测评结果

测评记录

Second Level

但是,作为一名优秀的OIer,我们不能拘泥于此! 那是不可能的
这个code确实可以AC,但是就没有更优的解法了吗?
明显可以有——

滚动数组!

Last modification:October 1st, 2019 at 12:49 pm
东北小蟹蟹已经穷的叮当都响不了啦!!qwq

Leave a Comment