[已解决]过河卒

柿子饼同学

在此 --->https://www.luogu.com.cn/problem/P1002

#include <bits/stdc++.h>
using namespace std;
int n, m, a, b;
int horse[][2] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};

int main(){
        scanf("%d%d%d%d", &n, &m, &a, &b);
        int m1[m+2][n+2];
        m1[0][0] = 1;
        m1[0][1] = 1;
        m1[1][0] = 1; 
        bool map[m+2][n+2] = {1};
        map[a][b] = 0;
        for(int i = 0; i < 8; i++){
                map[a+horse[i][0]][b+horse[i][1]] = 0;
        }
        for(int i = 2; i < m; i++){
                for(int j = 2; j < n; j++){
                        if(!map[i][j]){
                                continue;
                        }
                        m1[i][j] = m1[i-1][j] + m1[i][j-1]; 
                }
        }
        printf("%d", m1[m][n]);
        
        return 0;
}

那啥 , 感觉我代码没啥问题 , 但是它就不输出了
思路是 , 用二维数组弄一个坐标系出来 , 把马和他的控制点标为 0 , 其他是 1 .然后用转移方程得到 F(x, y) = F(x-1, y) + F(x, y-1) , F()是走到这个点的所有方法之和

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-3-29 22:17:14

柿子饼同学 发表于 2022-3-29 22:10
那 , 12 - 17行的为什么可以这样 , 怎么可以传入一个数组呢

12 - 17行就只是普通数组，比如：

int A[5] = {1, 2, 3, 4, 5};
float B[5] = {1.1, 2.2, 3.3, 4.4, 5.5};
char C[5] = {'A', 'B', 'C', 'D', 'E'};
Point D[5] = {{xxxxx}, {xxxxx}, ......... } // 数组里面装的就是 Point 构造

跳转到最佳答案楼层

傻眼貓咪

试试这个：

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

typedef struct Point{
        int r, c; // 行列
        Point(){}
        Point(int a, int b): r(a), c(b){}
}P;

// 马移动步数
P arr[8] = {
        {-2, 1}, {-2, -1},
        {-1, 2}, {-1, -2},
        {1, 2}, {1, -2},
        {2, 1}, {2, -1}
};
std::vector<P> Knights(arr, arr+8);

int moves(P A, P B){
        // 马控制点
        for(const P &K: Knights){
                if(A.r == K.r && A.c == K.c) return 0;
        }
        // 越界
        if(A.r > B.r || A.c > B.c) return 0;
        // 抵达终点
        else if(A.r == B.r && A.c == B.c) return 1;

        P A1(A.r+1, A.c); // 卒向下走
        P A2(A.r, A.c+1); // 卒向右走
        return moves(A1, B) + moves(A2, B);
}

int main(){
        P A(0, 0), B, K;
        std::cin
                >> B.r >> B.c // 终点(也就是边界)
                >> K.r >> K.c; // 马(骑士 Knight)
                
        // 八个马控制点
        for(P &k: Knights){
                k.r += K.r;
                k.c += K.c;
        }
        
        Knights.push_back(K); // 包括马原本位置，一共 9 个控制点
        std::cout << moves(A, B) << std::endl;
        
        return 0;
}

柿子饼同学

傻眼貓咪 发表于 2022-3-22 16:09
试试这个：

STL还没学这个...
话说deque就只是vector的升级版嘛

柿子饼同学

傻眼貓咪 发表于 2022-3-22 16:09
试试这个：

5 - 9 行的结构体定义中 , Point()是干嘛的 , 有点不懂

柿子饼同学

傻眼貓咪 发表于 2022-3-22 16:09
试试这个：

18行 vector 的定义中 , 不是 (元素个数 , 默认值) 的形式嘛
为什么可以引入一个数组
然后12行为什么可以这么写

柿子饼同学

傻眼貓咪 发表于 2022-3-22 16:09
试试这个：

哈哈哈哈感觉这是我们水平离得最近的一次
你代码跑了一下 , 两个对 , 三个超时
不过比我厉害多了

傻眼貓咪

柿子饼同学 发表于 2022-3-29 16:35
5 - 9 行的结构体定义中 , Point()是干嘛的 , 有点不懂

这是 C++ 和 C 构造的不同之处，这是构造函数，当你创建 Point 时，就会这个执行代码，我写了 2 个构造函数：Point(){} 和 Point(int a, int b): r(a), c(b){}，视你创建 Point 时的情况自动调用，
第一种：Point(){} 没有任何参数，不做任何改变
第二种：Point(int a, int b): r(a), c(b){}，当你创建 Point 时，加上 2 个参数，调用这个，会自动赋值 r 和 c 成员，类似 Python 里的 class 里面的 __init__(self) 一样。
C++

typedef struct Point{
        int r, c; // 行列
        Point(){}
        Point(int a, int b): r(a), c(b){}
}P;

Python

class Point:
    def __init__(self, a = None, b = None):
        self.r = a
        self.c = b

傻眼貓咪

柿子饼同学 发表于 2022-3-29 16:38
18行 vector 的定义中 , 不是 (元素个数 , 默认值) 的形式嘛
为什么可以引入一个数组
然后12行为什么可 ...

这是 vector 其中一种的初始化方法，vector 有很多初始化方法的，你可以创建空 vector（不定长），也可以创建有长度的 vector，也可以创建并且赋值的 vector。而我的代码中第 18 行用的是将数组 arr 里的元素全部拷贝给 vector，其用法构造如：std::vector<类型> 标识 (数组指针，数组指针往后移多少位，如果想拷贝全部元素，则 + 元素数量即可）

第 12 行是构造 Point 简写了，因为我懒，所以用 typedef 将 Point 构造名字换成 P 字。

傻眼貓咪

柿子饼同学 发表于 2022-3-29 16:40
哈哈哈哈感觉这是我们水平离得最近的一次
你代码跑了一下 , 两个对 , 三个超时
不 ...

很快能超越我的，我比较迟钝，需要重复学习很久才会。

柿子饼同学

傻眼貓咪 发表于 2022-3-29 18:10
这是 C++ 和 C 构造的不同之处，这是构造函数，当你创建 Point 时，就会这个执行代码，我写了 2 个构造 ...

哇 , python里类和对象我学过!
那后面大括号里是放什么的呢

柿子饼同学

傻眼貓咪 发表于 2022-3-29 18:18
这是 vector 其中一种的初始化方法，vector 有很多初始化方法的，你可以创建空 vector（不定长），也可以 ...

噢噢噢噢我忘记数组名是指针了

柿子饼同学

傻眼貓咪 发表于 2022-3-22 16:09
试试这个：

那 , 12 - 17行的为什么可以这样 , 怎么可以传入一个数组呢

傻眼貓咪

柿子饼同学 发表于 2022-3-29 22:04
哇 , python里类和对象我学过!
那后面大括号里是放什么的呢

括号里可以写你想初始化的代码，但我只想初始成员 r 和 c，所以括号里面空着。比如：

你也可以这样写

Point(int a, int b){
    r = a*a*2;
    c = b*2+6;
}

傻眼貓咪

柿子饼同学 发表于 2022-3-29 22:10
那 , 12 - 17行的为什么可以这样 , 怎么可以传入一个数组呢

12 - 17行就只是普通数组，比如：

int A[5] = {1, 2, 3, 4, 5};
float B[5] = {1.1, 2.2, 3.3, 4.4, 5.5};
char C[5] = {'A', 'B', 'C', 'D', 'E'};
Point D[5] = {{xxxxx}, {xxxxx}, ......... } // 数组里面装的就是 Point 构造

柿子饼同学

傻眼貓咪 发表于 2022-3-29 22:17
12 - 17行就只是普通数组，比如：

int A[5] = {1, 2, 3, 4, 5};

代码终于懂啦 , 感谢~