#include <iostream>
using namespace std;
int path[6][6];
int row,col,v,h;
bool OK(int i,int j)
{
if(i>=0 && i<row && j>=0 && j<col)
return true;
return false;
}
void DFS(int i,int j,int & counts)
{
if(path[i][j]==1)
{
if(i==v && j==h)
counts++;
return ;
}
path[i][j]=1;
if(OK(i-2,j-1))
DFS(i-2,j-1,counts);
if(OK(i-2,j+1))
DFS(i-2,j+1,counts);
if(OK(i-1,j-2))
DFS(i-1,j-2,counts);
if(OK(i+1,j-2))
DFS(i+1,j-2,counts);
if(OK(i-1,j+2))
DFS(i-1,j+2,counts);
if(OK(i+1,j+2))
DFS(i+1,j+2,counts);
if(OK(i+2,j-1))
DFS(i+2,j-1,counts);
if(OK(i+2,j+1))
DFS(i+2,j+1,counts);
path[i][j]=0;
}
int main()
{
freopen("s.txt","r",stdin);
freopen("key.txt","w",stdout);
while(cin>>row>>col>>v>>h)
{
memset(path,0,sizeof(path));
int counts=0;
DFS(v,h,counts);
cout<<counts<<endl;
}
return 0;
}
On a chess board sizes of m*n(1<=m<=5,1<=n<=5),given a start position,work out the amount of all the different paths through which the horse could return to the start position.(The position that the horse passed in one path must be different.The horse jumps in a way like "日")
Input
The input consists of several test cases.The size of the chess board m,n(row,column),and the start position v,h(vertical , horizontal) ,separated by a space.The left-up point is (0,0)
Output
the amount of the paths in a single line
Sample Input
5 4 3 1
Sample output
4596
解析：
马走日，八个方向，
不允许某条路径上重复。
if(path[i][j]==1)
{
if(i==v && j==h)
counts++;
//重复的如果是出发点，返回值
return ;//无论怎样，只要重复就返回
}
posted on 2009-06-28 18:11
luis 阅读(178)
评论(0) 编辑 收藏 引用 所属分类:
搜索