洛谷 P1002 [NOIP2002 普及组] 过河卒 （DFS+记忆递归）

原题链接

题目描述

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A 点 (0, 0)、B 点 (n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 B 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

输入输出样例

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

说明/提示

对于 100 \%100% 的数据，1 ≤ n,m ≤ 20，0 ≤ 马的坐标 ≤ 20。

 

首先别问为什么不用DP，问就是不会DP。（在学了在学了）

 

题目大意：在一个二维坐标系的A点有一个卒，B点是卒的目的地，C是对方的马，问如果卒只能往下和往有右走，那么有多少条线路可以到达B点。

 

最开始的想法，用DFS从(0,0)点开始递归搜索，搜索到B点后使结果 + 1。

#include

using namespace std;

const int N = 30;

int q[N][N];

int ax,ay,bx,by,cx,cy;

int ans;

void dfs (int x,int y){
    if(x < 0 || y < 0 || x > bx ||y > by)return ;
    
    if(x == bx && y == by){
        ans ++;
        return ;
    }

    if(q[x + 1][y] == 0){
        q[x][y] = 1;//防止后面递归的时候再次进过这个点
        dfs(x + 1,y);
    }
    q[x][y] = 0;//记得回溯

    if(q[x][y + 1] == 0){
        q[x][y] = 1;
        dfs(x,y + 1);
    }
    q[x][y] = 0;

    return ;
}

int main(){
    
    int d1[8] = {-1,-2,-2,-1,1,2,2,1},d2[8] = {-2,-1,1,2,2,1,-1,-2};

    cin >> bx >> by >> cx >> cy;
//马的八个点设置为不能通过
    for(int i = 0;i < 8;i ++){
        if(cx + d1[i] >= 0 && cx + d1[i] <= bx && cy + d2[i] >= 0 && cy + d2[i] <= by)
            q[cx + d1[i]][cy + d2[i]] = 1;
    }
    q[cx][cy] = 1;//马本身的位置也不能过

    dfs(0,0);//开始暴力搜索，嘤嘤嘤~

    cout << ans;

    return 0;
}

诶，怎么超时了，吸口氧看看，还是有两个点过不了。

可恶，简单地算下最坏时间复杂度：2^20，这……显然过不了吧。

嗯~既然tag是DP，那就……

让递归带本备忘录上去继续搜索

#include
#define ll long long
using namespace std;

const int N = 30;

int q[N][N];
ll mem[N][N];

int ax,ay,bx,by,cx,cy;
//记得得用long long，他真的太大了
//递归公式：f(x,y) = if(!q[x][y + 1])f(x,y + 1) + if(!q[x + 1][y])f(x + 1,y)
ll dfs (int x,int y){
    if(x < 0 || y < 0 || x > bx ||y > by)return 0;
    
    if(mem[x][y] != 0) return mem[x][y];

    if(q[x + 1][y] == 0){
        q[x][y] = 1;
        mem[x][y] += dfs(x + 1,y);
    }
    q[x][y] = 0;

    if(q[x][y + 1] == 0){
        q[x][y] = 1;
        mem[x][y] += dfs(x ,y + 1);
    }
    q[x][y] = 0;

    if(x == bx && y == by){
        mem[x][y] = 1;
        return mem[x][y];
    }

    return mem[x][y];
}

int main(){
    
    int d1[8] = {-1,-2,-2,-1,1,2,2,1},d2[8] = {-2,-1,1,2,2,1,-1,-2};

    cin >> bx >> by >> cx >> cy;

    for(int i = 0;i < 8;i ++){
        if(cx + d1[i] >= 0 && cx + d1[i] <= bx && cy + d2[i] >= 0 && cy + d2[i] <= by)
            q[cx + d1[i]][cy + d2[i]] = 1;
    }
    q[cx][cy] = 1;

    cout << dfs(0,0);

    return 0;
}
错题集

相关

标签