题目地址:https://vijos.org/p/1121

题目描述

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

棋盘用坐标表示,A点(0, 0)、B点(n, m)(n, m为不超过15的整数),同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

思路1

DP完解
到达当前点的路径数 = 到达这个点左边的点的路径数 + 到达这个点右边的点的路径数

AC代码

/*************************************************************************
    > File Name: 1121.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Fri 01 May 2015 21:41:30 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int main()
{
    int Bx, By, Hx, Hy;
    static bool map[20][20];
    static int dp[20][20];
    while(scanf("%d%d%d%d", &Bx, &By, &Hx, &Hy) == 4) {
        memset(map, 1, sizeof(map));
        map[Hy][Hx] = map[Hy-2][Hx-1] = map[Hy-2][Hx+1] = map[Hy+2][Hx-1] = map[Hy+2][Hx+1] = false;
        map[Hy-1][Hx-2]  = map[Hy-1][Hx+2] = map[Hy+1][Hx-2] = map[Hy+1][Hx+2] = false;

        // for(int i=0; i<=Bx; ++i) {
            // for(int j=0; j<=By; ++j) {
                // cout << map[i][j] << " ";
            // }
        // cout << endl;
        // }

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int j=0; j<=By; ++j)
            for(int i=0; i<=Bx; ++i) {
                if(map[j][i]) {
                    if(i>0 && j>0)
                        dp[j][i] = dp[j-1][i] + dp[j][i-1];
                    if(j>0 && i==0)
                        dp[j][i] = dp[j-1][i];
                    if(i>0 && j==0)
                        dp[j][i] = dp[j][i-1];

                }
                else
                    dp[j][i] = 0;
            }
        printf("%d\n", dp[By][Bx]);
    }
    return 0;
}

思路2

上面的解法是我参考题解的DP做的,今早一起来用DFS给做出来了。。

太开心了,主递归:
int DFS(int x, int y) {
int d=0,r=0;
// printf(“(%d, %d)\n”, x, y);
if(x==Bx && y==By)
return 1;
if(m[y+1][x] && y+1<=By)
d=DFS(x, y+1);
if(m[y][x+1] && x+1<=Bx)
r=DFS(x+1, y);
return d+r;
}

AC代码2

/*************************************************************************
    > File Name: 1121.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Fri 01 May 2015 21:41:30 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int Bx, By, Hx, Hy;
static bool m[20][20];

int DFS(int x, int y)  {
    int d=0,r=0;
//    printf("(%d, %d)\n", x, y);
    if(x==Bx && y==By)
        return 1;
    if(m[y+1][x] && y+1<=By)
        d=DFS(x, y+1);
    if(m[y][x+1] && x+1<=Bx)
        r=DFS(x+1, y);
    return d+r;
}

int main()
{
    while(scanf("%d%d%d%d", &Bx, &By, &Hx, &Hy) == 4) {
        memset(m, 1, sizeof(m));
        m[Hy][Hx] = m[Hy-2][Hx-1] = m[Hy-2][Hx+1] = m[Hy+2][Hx-1] = m[Hy+2][Hx+1] = false;
        m[Hy-1][Hx-2]  = m[Hy-1][Hx+2] = m[Hy+1][Hx-2] = m[Hy+1][Hx+2] = false;

        printf("%d\n", DFS(0, 0));
    }
    return 0;
}