算法与数据结构---过河卒-搜索（递归）写法常见易错点

一、总结

一句话总结：

f[i][j]=f[i-1][j]+f[i][j-1]这样的递推表达式，取数之前一定要保证数是存在的

1、表示马的控制点如何表示？

int hx[9]={0,-2,-1,1,2,2,1,-1,-2};

int hy[9]={0,1,2,2,1,-1,-2,-2,-1};

2、边界条件不清晰易出错？

A、横轴f[i][0]=1(1<=i<=bx)和纵轴f[0][i]=1(1<=i<=by)是边界点，

B、f[i][by]和f[bx][i]并不是边界点

C、f[i][0]=1和f[0][i]=1做边界点会出错，因为当马的位置如果是(4,0)，那么(5,0)的位置本来是去不了的，

3、递归一般是由终止条件到达初始条件，比如过河卒？

那么递归的关系式应该是f[i][j]=f[i-1][j]+f[i][j-1]，而不是f[i][j]=f[i+1][j]+f[i][j+1]

4、这题（过河卒）的数据量是大于int的，所以定义缓存数组f的时候要用long long？

long long f[25][25];这题的数据量是大于int的，所以要用long long

5、这题（过河卒）的数据量是大于int的，所以递归函数的返回值要用long long，而不能是int？

int find(int x,int y){} 这样就是错的

//递归函数返回值的问题
int find(int x,int y){
    if(f[x][y]!=-1) return f[x][y];
    else{
        return f[x][y]=find(x-1,y)+find(x,y-1);
    }
}

6、如下初始化f[i][0]和f[0][i]会造成什么问题？

如果有马在中间，比如(4,0)，4后面的点本来是达不到的，但是如下初始化之后，是可以达到的，这样就出错了

|||-begin

初始状态：
马控制的点为0
f[0][0]=0
f[i][0]=1 (1<=i<=bx)
f[0][i]=1 (1<=i<=by)
//初始化f数组
f[0][0]=0;
for(int i=1;i<=bx;i++) f[i][0]=1;
for(int i=1;i<=by;i++) f[0][i]=1;

|||-end

7、f[i][j]=f[i-1][j]+f[i][j-1]这样的递推表达式，无论是做递归，还是做递推，要注意什么？

要保证i和j大于等于1，小于1的情况要单独分析，取数之前一定要保证数是存在的

二、过河卒-递归写法常见易错点

博客对应课程的视频位置：

1、题目描述

题目位置

P1002 过河卒 - 洛谷
https://www.luogu.com.cn/problem/P1002

2、代码

 1 /*
 2 
 3 卒子可以向下走和向右走
 4 
 5 如果没有这个马，搜索应该怎么做
 6 
 7 递归：
 8 递归的终止条件：起点
 9 递归的递推表达式：卒子可以向下走和向右走
10 （f[i][j]=f[i-1][j]+f[i][j-1]）
11 递归的返回值：路径条数
12 
13 
14 如果有马的情况
15 递归的终止条件：起点或者马控制的区域
16 
17 
18 A是A点 , B是B点, M是马的位置, X是被马拦着不能走的点
19 A 0 0 0 0 0 0
20 0 0 X 0 X 0 0
21 0 X 0 0 0 X 0
22 0 0 0 M 0 0 0
23 0 X 0 0 0 X 0
24 0 0 X 0 X 0 0
25 0 0 0 0 0 0 B
26 其中每个点的值代表的是当前这个点会有几条路径用过这个点
27 （路径指的是从A到B的路径）
28 
29 1 1 1 1 1 1 1
30 1 2 X 1 X 1 2
31 1 X 0 1 1 X 2
32 1 1 1 M 1 1 3
33 1 X 1 1 0 X 3
34 1 1 X 1 X 0 3
35 1 2 2 3 3 3 6
36 
37 
38 这里初始化的时候能直接初始化i=0和j=0对应的两条线么
39 不能，因为如果这样初始化后，当马的位置如果是(4,0)，
40 那么(5,0)的位置本来是去不了的，
41 但是这样初始化却会初始化为1
42 
43 
44 */
45 #include <iostream>
46 #include <cstring>
47 using namespace std;
48 int hx[9]={0,-2,-1,1,2,2,1,-1,-2};
49 int hy[9]={0,1,2,2,1,-1,-2,-2,-1};
50 long long f[25][25];
51 //递归函数返回值的问题
52 long long find(int x,int y){
53     if(f[x][y]!=-1) return f[x][y];
54     else{
55         if(x-1>=0&&y-1>=0) return f[x][y]=find(x-1,y)+find(x,y-1);
56         else if(x-1>=0) return f[x][y]=find(x-1,y);
57         else if(y-1>=0) return f[x][y]=find(x,y-1);
58         else return 0;   
59     }
60 }
61 
62 int main(){
63     int bx,by,mx,my;
64     cin>>bx>>by>>mx>>my;
65     //初始化f数组
66     memset(f,-1,sizeof(f));
67     f[0][0]=1;
68     //将马控制得到的位置初始化到f数组
69     for(int i=0;i<=8;i++){
70         //马的位置没出界
71         int now_x=mx+hx[i];
72         int now_y=my+hy[i];
73         if(now_x>=0&&now_x<=bx&&now_y>=0&&now_y<=by){
74             f[now_x][now_y]=0; 
75         }
76     }
77 
78     cout<<find(bx,by)<<endl;
79     return 0;
80 }