有一个方格子，A点在左下角，B点在右上角，求A点到B点的最短路径数量

博主的第十篇博客，特此标记纪念。

概述

有一个方格子，A点在左下角，B点在右上角，求A点到B点的最短路径有多少条。

思路

我们这里假设方格子是8*8的方格。题目有时会混淆，A和B有没有占用左下角和右上角的方格。这里我们的解题认为没有占用。

思路一：
A到B就需要走16步，8步横走，8步竖走。这在排列组合中，使用公式c(16,8)很容易得出答案，这里我们用算法实现。我们使用回溯法解题。

思路二：（来自网络，我觉得挺有意思，这里未贴源码）
A点到B点的最短路径肯定是16，其中8步横走，8步竖走，设横走为’1’，竖走为’0’，那么最短路径是一个16位的二进制字符串。只要一个16位二进制字符串里面有8个’1’，或者8个’0’，那么这个二进制字符串就是一条可行的最短路径。

源码

本文主要是以C、C++、QT为基础进行编程，运行前简单修改即可。测试入口函数为 void Test_ShortestPath()。

static quint32 gAccount = 0;//用于保存结果
static quint8 NeedNum = 8;//用于表示方格尺寸
void ShortestPath(quint8 row, quint8 col)
{
    if(row<NeedNum)
    {
        ShortestPath(row+1,col);
    }

    if(col<NeedNum)
    {
        ShortestPath(row,col+1);
    }

    if(row == NeedNum && col == NeedNum)
    {
        gAccount++;
        return;
    }
}
void Test_ShortestPath()
{
    ShortestPath(0, 0);
    qDebug()<<"gAccount:"<<gAccount;
}

运行结果

gAccount: 12870