风的方向
厚德致远,博学敦行!
posts - 52,comments - 21,trackbacks - 0

马的走法

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;
}


 

posted on 2010-09-19 10:03 jince 阅读(408) 评论(2)  编辑 收藏 引用 所属分类: Questions

FeedBack:
# re: 马的走法
2011-08-20 16:35 | 水中鱼
如果直接直接返回,怎么办,没看到您的处理啊
  回复  更多评论
  
# re: 马的走法[未登录]
2011-08-20 22:30 | jince
@水中鱼
请看清题意!  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理