搜索——马的遍历

问题 L: 马的遍历

时间限制: 1 Sec  内存限制: 128 MB
提交: 85  解决: 45
[提交][状态][讨论版][命题人:quanxing]

题目描述

   中国象棋半张棋盘如图4（a）所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如图4（a）中所示为一种跳行路线，并将所经路线打印出来。打印格式为：0,0->2,1->3,3->1,4->3,5->2,7->4,8…

 

 

输入

无输入

输出

输出上述棋盘的可以从（0,0）走到（4,8）点的方案数。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
int sum=0;
int dir[4][2]={2,1,1,2,-1,2,-2,1};
void dfs(int x,int y)
{
	if(x==4&&y==8)
	{
		sum++;
		return;
	}
	for(int i=0;i<4;i++)
	{
		x+=dir[i][0];
		y+=dir[i][1];
		if(x<=4&&x>=0&&y<=8&&y>=0)
		dfs(x,y);
		x-=dir[i][0];
		y-=dir[i][1];
	}
}
int main()
{
    dfs(0,0);
    cout<<sum<<endl;
    return 0;
}