過(guò)河卒
Time Limit:1000MS Memory Limit:65536K
Total Submit:691 Accepted:155
Description
棋盤上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤上的任一點(diǎn)有一個(gè)對(duì)方的馬（如C點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)，如圖中的C點(diǎn)和P1，……，P8，卒不能通過(guò)對(duì)方馬的控制點(diǎn)。棋盤用坐標(biāo)表示，A點(diǎn)(0,0)、B點(diǎn)(n, m) (n,m為不超過(guò)20的整數(shù)),同樣馬的位置坐標(biāo)是需要給出的，C≠A且C≠B?，F(xiàn)在要求你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)。
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
多個(gè)測(cè)試案例，每個(gè)案例一行，處理到文件末尾
B點(diǎn)坐標(biāo)（n,m）以及對(duì)馬的坐標(biāo)（X,Y）{不用判錯(cuò)}
Output
一個(gè)整數(shù)(路徑的條數(shù))
Sample Input
6 6 3 2
Sample Output
17
這個(gè)題目還是不錯(cuò)的。。。
代碼如下：
#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++)//計(jì)算受馬控制的點(diǎn)
{
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++)//計(jì)算一個(gè)點(diǎn)上的走法，上方點(diǎn)的走法數(shù)+左方點(diǎn)的走法數(shù)
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 閱讀(2140)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
Questions