洛谷-P１００２

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

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

img

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
int x,y,mx,my;
long long a[30][30],map[30][30];//地图位置
using namespace std;
void bj(int mmx,int mmy)
{
    map[mmx][mmy]=1;
    map[mmx-1][mmy-2]=1;
    map[mmx-2][mmy-1]=1;
    map[mmx-2][mmy+1]=1;
    map[mmx-1][mmy+2]=1;
    map[mmx+1][mmy-2]=1;
    map[mmx+2][mmy-1]=1;
    map[mmx+2][mmy+1]=1;
    map[mmx+1][mmy+2]=1;
}//被控制点位
int main()
{
    int i,j;
    a[1][0]=1;
    cin>>x>>y>>mx>>my;
    bj(mx,my);//调用
    for(i=1;i<=x+1;i++)//x+1移动位置,避免负数,下同
    {    for(j=1;j<=y+1;j++)
        {
           a[i][j]=a[i-1][j]+a[i][j-1];//加法原理
			if(map[i-1][j-1])a[i][j]=0;
        }
    }   
    cout<<a[x+1][y+1];
    return 0;
}

解题思想

1.递推

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

2.加法原理

加法原理是分类计数原理，常用于排列组合中，具体是指：做一件事，完成它可以有img类方法，在第一类方法中有img种不同方法，在第二类方法中有img种不同方法，……，在第img类方法中有img种不同方法，那么完成这件事共有img种不同的方法。

3.动态分配

动态分配是指在程序运行过程中根据需要动态地分配内存空间。在静态分配中，程序在编译时就已经确定了变量的内存空间大小，而在动态分配中，程序可以根据实际需要动态地分配所需的内存空间，这样可以更加灵活地使用内存，避免浪费。在C++中，可以使用new关键字动态分配内存，使用delete关键字释放内存。在Java中，可以使用new关键字动态分配内存，但是Java具有自动内存管理机制，所以不需要手动释放内存，由垃圾回收机制来回收没有被使用的内存空间。

4.避免越界

越界是指访问数组或指针指向的内存空间时，访问了超过其边界的部分，这种行为是不安全的，可能会导致程序崩溃、数据丢失等问题。为了避免越界，可以采取以下措施：

  1. 在编写代码时，要注意数组和指针的边界，不要越界访问。

  2. 使用一些工具来辅助检测越界问题，例如静态代码分析工具、动态内存分析工具、代码审查等。

  3. 对于数组和指针的访问，可以使用一些防止越界的技术，例如使用STL容器代替原生数组、使用智能指针代替裸指针、使用异常处理机制等。

  4. 在使用数组和指针时，要注意变量的范围和生命周期，避免因为变量已经被销毁而导致访问已经失效的内存空间。

  5. 如果需要访问超过数组或指针边界之外的内存空间，可以考虑使用边界检查技术或者使用安全的库函数，例如memcpy_s、strncpy_s等。