#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 閱讀(208)
評論(0) 編輯 收藏 引用 所屬分類:
搜索