题目背景
在爱与愁的故事第一弹第三章出来前先练练四道基本的回溯/搜索题吧……
题目描述
中国象棋半张棋盘如图 1所示。马自左下角 (0,0) 向右上角 (m,n) 跳。规定只能往右跳,不准往左跳。比如图 1中所示为一种跳行路线,并将路径总数打印出来。
输入格式
只有一行:两个数 n,m。
输出格式
只有一个数:总方案数 total。
输入输出样例
输入 #1
4 8
输出 #1
37
#include<bits/stdc++.h>
using namespace std;
int n,m,t=0;
int dx[4]={2,1,-1,-2};//四个方向
int dy[4]={1,2,2,1};
bool a[25][25];//判断有没有重复
void dfs(int x,int y)
{if(x==n&&y==m)//判断路线{t++;//增加一条路线return;//结束}for(int i=0;i<4;i++){int xx=x+dx[i];//新的坐标int yy=y+dy[i];if(xx>=0&&xx<=n&&yy>=0&&yy<=m&&!a[xx][yy])//如果没超过边界且不重复{a[xx][yy]=true;//标记路线dfs(xx,yy);//继续搜索a[xx][yy]=false;//回溯}}
}
int main()
{cin>>n>>m;a[0][0]=true;dfs(0,0);//从0,0开始搜索cout<<t;return 0;
}