822. Walk the Grid

题目

给定一个 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++;//If the current position is at the end point
    else
    {
    
        if(x < n) dfs(x+1,y);//如果可以往下走
        if(y < m) dfs(x, y+1);//Go right if you can
    }
}

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

    return 0;
}

Array simulation wide search,爆内存

#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;
}