822. 走方格

题目

给定一个 n×m 的方格阵，沿着方格的边线走，从左上角 (0,0) 开始，每次只能往右或者往下走一个单位距离，问走到右下角 (n,m) 一共有多少种不同的走法。

输入格式
共一行，包含两个整数 n 和 m。

输出格式
共一行，包含一个整数，表示走法数量。

数据范围
1≤n,m≤10
输入样例：
2 3
输出样例：
10

深搜代码AC

#include <iostream>

using namespace std;

int n, m;
int res;
void dfs(int x, int y)
{
    
    if(x == n && y == m)res++;//如果当前位置在终点
    else
    {
    
        if(x < n) dfs(x+1,y);//如果可以往下走
        if(y < m) dfs(x, y+1);//如果可以往右走
    }
}

int main()
{
    
    cin >> n >> m;
    dfs(0,0);
    cout << res << endl;

    return 0;
}

数组模拟广搜，爆内存

#include <iostream>

using namespace std;
const int N = 15;

int dx[] = {
    0,1}, dy[] = {
    1,0};

int bfs(int x, int y)
{
    
    int res = 0;
    int q[1000][2] = {
    0};
    int f = 0, t = 0;
    q[t][0] = 0, q[t][1] = 0;
    t++;
    while(f != t)
    {
    
        int curX = q[f][0], curY = q[f][1];
        f++;
        if(curX == x && curY == y)res++;
        for(int i = 0; i < 2; i++)
        {
    
            int tX = curX + dx[i], tY = curY + dy[i];
            if(tX >= 0 && tX <= x && tY >= 0 && tY <= y)
            {
    
                q[t][0] = tX, q[t][1] = tY;
                t++;
            }
        }
    }
    return res;
}

int main()
{
    
    int n, m;
    cin >> n >> m;
    cout << bfs(n,m) << endl;

    return 0;
}