2390: Tired Horse
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 |
3s | 8192K | 168 | 89 | Standard |
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
Problem Source: provided by slp3
This problem is used for contest: 82
#include<stdio.h>
#include<string.h>
int map[10][10];
int row,colum,gi,gj;
int xx[8]={1,2, 2, 1,-1,-2,-2,-1};
int yy[8]={2,1,-1,-2,-2,-1,1,2};
int count;
void dfs(int x,int y)
{
if(map[x][y])
{
if(x==gi&&y==gj) count++;
return ;
}
int i;
map[x][y]=1;
for(i=0;i<8;i++)
{
if(x+xx[i]<0||x+xx[i]>=row||y+yy[i]<0||y+yy[i]>=colum) continue;
dfs(x+xx[i],y+yy[i]);
}
map[x][y]=0;
}
int main()
{
int i;
while(scanf("%d%d%d%d",&row,&colum,&gi,&gj)==4)
{
memset(map,0,sizeof(map));
count=0;
dfs(gi,gj);
printf("%d/n",count);
}
return 0;
}