一、问题描述

二、问题分析

        自己的想法是将两个条件拆开计算，因为第二个条件的独立计算比较简单，将所有在对角线汇合的点的可能相加就可，然后对于第一个条件就进行递归搜索，记录在同一直线上的次数，在抵达目标端点时，若次数等于2时（书中实现使用的是大于等于2，于是在下面的实现中也进行了统一）总计数值加一，但是这样计算可能会有重复计数，当两人相交后，继续沿同一直线前进时（一人向上，一人向下）。

        原书中的是实现则更加巧妙，对于两种情况，将其合并实现。对于第二种情况来说，其本质上属于第一情况，相交意味值两点同时在横竖两条直线上，这样将横纵坐标分别计数就被归类为第一种情况，统一了实现条件，便于代码实现。

三、代码实现

1.C/C++实现

#include 
#include 
#include 
#include 
#include 
#include 
#include 
 
using namespace std;
 
const int N = 6;
 
int get_count(int x, int y, int p, int q, int meet)
{
	if (x > N || y > N || p < 0 || q < 0)  // 越界
		return 0;
	if (x == N && y == N && meet >= 2)  // 满足条件
		return 1;
	if (x == p)
		meet++;
	if (y == q)
		meet++;
	int count = 0;
	count += get_count(x + 1, y, p - 1, q, meet);
	count += get_count(x + 1, y, p, q - 1, meet);
	count += get_count(x, y + 1, p - 1, q, meet);
	count += get_count(x, y + 1, p, q - 1, meet);
	return count;
}
 
int main()
{
 
	cout << get_count(0, 0, N, N, 0) << endl;
	
	return 0;
}

2.Python实现

# codiNg = utf-8
 
N = 6
 
 
def get_count(x, y, p, q, meet):
    if x > N or y > N or p < 0 or q < 0:
        return 0
    if x == N and y == N and meet >= 2:
        return 1
    if x == p:
        meet += 1
    if y == q:
        meet += 1
    count = 0
    count += get_count(x + 1, y, p - 1, q, meet)
    count += get_count(x, y + 1, p - 1, q, meet)
    count += get_count(x + 1, y, p, q - 1, meet)
    count += get_count(x, y + 1, p, q - 1, meet)
    return count
 
 
if __name__ == '__main__':
    print(get_count(0, 0, N, N, 0))
    pass