49. 跳马问题
★ 输入文件：horse.in 输出文件：horse.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
有一只中国象棋中的 “ 马 ” ，在半张棋盘的左上角出发，向右下角跳去。规定只许向右跳（可上，可下， 但不允许向左跳）。请编程求从起点 A(1,1) 到终点 B(m,n) 共有多少种不同跳法。
【输入格式】
输入文件只有一行，两个整数m和n（1≤m,n≤20），两个数之间有一个空格。
【输出格式】
输出文件只有一个整数，即从 A 到 B 全部的走法。
【输入输出样例】
输入文件(horse.in)
5 9
输出文件(horse.out)
37
思路：宽搜。
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans;
int vis[][];
struct nond{
int x,y;
};
queue<nond>que;
int dx[]={,-,,-};
int dy[]={,,,};
int main(){
freopen("horse.in","r",stdin);
freopen("horse.out","w",stdout);
scanf("%d%d",&n,&m);
nond be;
be.x=;be.y=;
que.push(be);
while(!que.empty()){
nond now=que.front();
que.pop();
for(int i=;i<;i++){
int cx=now.x+dx[i];
int cy=now.y+dy[i];
if(cx==n&&cy==m) ans++;
else if(cx>=&&cx<=n&&cy>=&&cy<=m){
nond cc;
cc.x=cx;
cc.y=cy;
que.push(cc);
}
}
}
printf("%d",ans);
}