馬的走法

Time Limit:1000MS  Memory Limit:65536K
Total Submit:127 Accepted:80

Description

在一個4*5的棋盤上，輸入馬的起始位置坐標（縱、橫），求馬能返回初始位置的所有不同走法的總數（馬走過的位置不能重復,馬走“日”字）。

Input

多個測試數據。
每組2個數字

Output

輸出不同走法的總數。

Sample Input

2 2

Sample Output

4596

               窮舉法！也可以看做深搜！角度不同。。這與前面一題過河卒不同，在過河卒中如果用深搜的話會超時，我試過了。。。
代碼如下：

#include<stdio.h>
#include<string.h>
int count;
int s[4][5];
int a[8]={-2,-2,-1,-1,1,1,2,2};
int b[8]={1,-1,2,-2,2,-2,1,-1};
int x1,y1;
void fun(int x,int y)
{
    int i;
    int x2,y2;
    for(i=0;i<8;i++)
    {
        x2=x+a[i];
        y2=y+b[i];
        if((x2>=0)&&(y2>=0)&&(y2<=4)&&(x2<=3)&&(s[x2][y2]==0))
        {
            s[x2][y2]=1;
            fun(x2,y2);
            s[x2][y2]=0;
        }
        else if((x2==x1)&&(y2==y1))
            count++;
    }
}
int main()
{

    while((scanf("%d %d",&x1,&y1)!=EOF))
    {
        count=0;
        if((x1<=4)&&(y1<=5)&&(y1>0)&&(x1>0))
        {
            x1=x1-1;
            y1=y1-1;
            memset(s,0,sizeof(s));
            s[x1][y1]=1;
            fun(x1,y1);
            printf("%d\n",count);
        }
        else
        {
            printf("%d\n",count);
        }
    }
    return 0;
}