题目描述

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

输入格式

共一行，包含两个整数n和m。

输出格式

共一行，包含一个整数，表示走法数量。

数据范围

1≤n,m≤10

样例输入

2 3

样例输出

10

方案一：dfs(深搜) 时间复杂度:O(n)吧？

#include <bits/stdc++.h>
using namespace std;
int n,m;
bool mp[31][31];
int dx[2]= {0,1};
int dy[2]= {1,0};
int ans=0;
void dfs(int x,int y)
{
  if(x>n or  y>m)return;
  if(x==n and y==m)
  {
    ans++;
    return;
  }
  for(int i=0; i<2; i++)
  {
    int tmpx=x+dx[i],tmpy=y+dy[i];
    if(mp[tmpx][tmpy])
    {
      mp[tmpx][tmpy]=false;
      dfs(tmpx,tmpy);
      mp[tmpx][tmpy]=true;
    }
  }
}
int main()
{
  memset(mp,true,sizeof(mp));
  scanf("%d%d",&n,&m);
  dfs(0,0);
  printf("%d",ans);
  return 0;
}

解释

因为只用输出方案数，所以可以用深搜 ps:绝对不是广搜不会!!!
起点是(0,0),终点是(n,m)。
只能往下或者往右走(毕竟其他的方向没用)。
所以dx数组为{1,0},dy数组为{0,1}。
dfs里面第一行是剪枝实际没有作用……
mp是记录这一个点是否被访问过(一定要记得回溯!)
如果x==n,y==m的话就是到达终点了,ans要加一。
dfs的初始值为0,0<一定要记住>。
这道题数据范围较小,如果过大可能会爆栈(在一些重大考试中如果遇到同类谨慎使用！)