题目描述:
试求 n × m 的方格图形中, 从点 (0, 0) 到点 (n, m) 的最短路径数目.
输入描述:
有多组测试数据. 输入的第一行为一个正整数 N, 表示接下来有 N 组测试数据.
在接下来的每行输入中有两个 32 位无符号整数 n 和 m, 表示该方格图形的大小.
输出描述:
对于每组测试数据, 输出一行答案, 即符合要求的最短路径数.
样例输入:
2
5 4
1 1
样例输出:
126
2
题解: 这题一看就是一道 DFS 水题直接深搜一下就出来了, 废话不多说, 直接上代码
代码:
- #include<iostream>
- using namespace std;
- long ans;
- long m,n;
- void dfs(int x,int y){
- if(x==n&&y==m){
- ans++;
- return ;
- }
- if(x<n)
- dfs(x+1,y);
- if(y<m)
- dfs(x,y+1);
- }
- int main(){
- int T;
- while(cin>>T){
- while(T--){
- cin>>n>>m;
- if(n==0&&m==0)
- break;
- else{
- ans=0;
- dfs(0,0);
- cout<<ans<<endl;}
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2742714.html