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

过河卒

Time Limit:1000MS  Memory Limit:65536K
Total Submit:691 Accepted:155

Description

棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点,如图中的C点和P1,……,P8,卒不能通过对方马的控制点。棋盘用坐标表示,A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的,C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。


1 2 3 4 5 6 7 8
A +---+---+---o---+---o---+---+----+--------->Y
| | | | | | | | |
1 +---+---o---+---+---+---o---+----+
| | | | | | | | |
2 +---+---+---+---C---+---+---+----+
| | | | | | | | |
3 +---+---o---+---+---+---o---+----+
| | | | | | | | |
4 +---+---+---o---+---o---+---+----+ B(4,8)
|
|
V

X

 

Input

多个测试案例,每个案例一行,处理到文件末尾
B点坐标(n,m)以及对马的坐标(X,Y){不用判错}

Output

一个整数(路径的条数)

Sample Input

6 6 3 2 

 

Sample Output

17
         这个题目还是不错的。。。
代码如下:
#include<stdio.h>


int s[21][21];
__int64 c[
21][21];


int a0[8]={-2,-2,-1,-1,1,1,2,2};
int b0[8]={1,-1,2,-2,2,-2,1,-1};

int x1,y1;
int x3,y3;

int main()
{
    
int x2,y2;
    
int i,j;
    
int test;
    
while((scanf("%d %d %d %d",&x1,&y1,&x3,&y3)!=EOF))
    
{

        
for(i=0;i<21;i++)
            
for(j=0;j<21;j++)
            
{
                s[i][j]
=1;
                c[i][j]
=0;
            }

        s[x3][y3]
=0;
        
for(i=0;i<8;i++)//计算受马控制的点
        {
            x2
=x3+a0[i];
            y2
=y3+b0[i];
            
if((x2>=0)&&(y2>=0)&&(y2<=20)&&(x2<=20))
            
{
                s[x2][y2]
=0;
            }

        }



        test
=1;
        
for(j=0;j<21;j++)//初始化边上的走法
        {
            
if(test)
            
{
                
if(s[0][j]==0)
                
{
                    test
=0;
                }

                
else
                
{
                    c[
0][j]=1;
                }

            }


        }

        test
=1;
        
for(j=0;j<21;j++)
        
{
            
if(test)
            
{
                
if(s[j][0]==0)
                
{
                    test
=0;
                }

                
else
                
{
                    c[j][
0]=1;
                }

            }

        }



        
for(i=1;i<21;i++)//计算一个点上的走法,上方点的走法数+左方点的走法数
            for(j=1;j<21;j++)
            
{
                
if(s[i][j])
                
{
                    
                    c[i][j]
=c[i-1][j]*s[i-1][j]+c[i][j-1]*s[i][j-1];
                }

            }

        

            printf(
"%I64d\n",c[x1][y1]); 
    }

    
return 0;
}


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

FeedBack:
# re: 过河卒
2015-06-15 20:54 | cs
不能过  回复  更多评论
  
# re: 过河卒[未登录]
2015-06-15 21:06 | jince
@cs
什么都百度要脑袋有嘛用~兄弟~
  回复  更多评论
  

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