作者Qoooooo (Qoo)
站內C_and_CPP
標題[問題] 騎士問題 C
時間Thu May 14 17:09:37 2009
目前在自學的我寫到騎士問題
但我的騎士不論從哪一步開始走，都會一格走不到!!!
所以想請教各位我是哪邊出問題了@@"謝謝各位
下面是我的code，寫得蠻暴力的~請多見諒
#include <stdio.h>
#include <stdlib.h>
int A[12][12];
int B[8];
int knight(int,int);
int kni(int,int);
int zero();
int y,z,j,a,b,g=0;
int min=10;
int main(void)
{
for(a=0;a<12;a++)
for(b=0;b<12;b++)
A[a][b]=0;
for(a=0;a<2;a++)
for(b=0;b<12;b++)
A[a][b]=1;
for(b=0;b<2;b++)
for(a=0;a<12;a++)
A[a][b]=1;
for(a=10;a<12;a++)
for(b=0;b<12;b++)
A[a][b]=1;
for(b=10;b<12;b++)
for(a=0;a<12;a++)
A[a][b]=1;
for(a=0;a<12;a++)
{
for(b=0;b<12;b++)
printf("%d ",A[a][b]);
printf("\n");
}
do
{
printf("This is 8 * 8!!!please keyin your knight location: ");
scanf("%d%d",&a,&b);
}
while(a<1||a>8||b<1||b>8);
printf("(%d,%d)\n",a,b);
a=a+1;
b=b+1;
A[a][b]=1;
knight(a,b);
for(a=0;a<12;a++)
{
for(b=0;b<12;b++)
printf("%d ",A[a][b]);
printf("\n");
}
system("pause");
}
int knight(int a,int b)
{
for(y=0;y<8;y++)
B[y]=0;
min=10;
while(g!=63)
{
if(a+1>1&&a+1<10&&b+2>1&&b+2<10&&(A[a+1][b+2]!=1))
B[0]=kni(a+1,b+2);
if(a+2>1&&a+2<10&&b+1>1&&b+1<10&&(A[a+2][b+1]!=1))
B[1]=kni(a+2,b+1);
if(a+2>1&&a+2<10&&b-1>1&&b-1<10&&(A[a+2][b-1]!=1))
B[2]=kni(a+2,b-1);
if(a+1>1&&a+1<10&&b-2>1&&b-2<10&&(A[a+1][b-2]!=1))
B[3]=kni(a+1,b-2);
if(a-1>1&&a-1<10&&b-2>1&&b-2<10&&(A[a-1][b-2]!=1))
B[4]=kni(a-1,b-2);
if(a-2>1&&a-2<10&&b-1>1&&b-1<10&&(A[a-2][b-1]!=1))
B[5]=kni(a-2,b-1);
if(a-2>1&&a-2<10&&b+1>1&&b+1<10&&(A[a-2][b+1]!=1))
B[6]=kni(a-2,b+1);
if(a-1>1&&a-1<10&&b+2>1&&b+2<10&&(A[a-1][b+2]!=1))
B[7]=kni(a-1,b+2);
for(y=0;y<8;y++)
{
if(B[y]==0)
B[y]=100;
if(B[y]<min)
{
min=B[y];
z=y;
}
printf("%d ",B[y]);
}
printf("\n%d\n",z);
if(min==10)
{
printf("error\n");
g++;
}
else if(z==0)
{
printf("(%d,%d)\n",a,b+1);
A[a+1][b+2]=1;
g++;
knight(a+1,b+2);
}
else if(z==1)
{
printf("(%d,%d)\n",a+1,b);
A[a+2][b+1]=1;
g++;
knight(a+2,b+1);
}
else if(z==2)
{
printf("(%d,%d)\n",a+1,b-2);
A[a+2][b-1]=1;
g++;
knight(a+2,b-1);
}
else if(z==3)
{
printf("(%d,%d)\n",a,b-3);
A[a+1][b-2]=1;
g++;
knight(a+1,b-2);
}
else if(z==4)
{
printf("(%d,%d)\n",a-2,b-3);
A[a-1][b-2]=1;
g++;
knight(a-1,b-2);
}
else if(z==5)
{
printf("(%d,%d)\n",a-3,b-2);
A[a-2][b-1]=1;
g++;
knight(a-2,b-1);
}
else if(z==6)
{
printf("(%d,%d)\n",a-3,b);
A[a-2][b+1]=1;
g++;
knight(a-2,b+1);
}
else if(z==7)
{
printf("(%d,%d)\n",a-2,b+1);
A[a-1][b+2]=1;
g++;
knight(a-1,b+2);
}
}
return;
}
int kni(int a,int b)
{
int j=0;
if(A[a+1][b+2]==0)
j++;
if(A[a+2][b+1]==0)
j++;
if(A[a+2][b-1]==0)
j++;
if(A[a+1][b-2]==0)
j++;
if(A[a-1][b-2]==0)
j++;
if(A[a-2][b-1]==0)
j++;
if(A[a-2][b+1]==0)
j++;
if(A[a-1][b+2]==0)
j++;
return j;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.85.1.44
1F：→ netsphere:我看過的騎士問題有1. 格子全部走完並最後回到起點 05/14 19:38
2F：→ netsphere: 2.走完全部格子就好 05/14 19:39
3F：→ netsphere:如果是2的話 用backtrack很容易就解決了 05/14 19:40
4F：→ Qoooooo:我是2~可是不論選擇從哪步開始總會少一格沒辦法走到 05/19 23:47