439 - Knight Moves

[cyfra]

Hi!

I have no idea why my program always gives WA.

When I am testing it everything is OK.

Please help...

Program p439;
VAR
ch,c1,c2:char;
zm1,zm2:longint;
wynik:longint;
tab:array[1..8,1..8] of longint;
d1,d2,w1,w2,w3,x,y,head,tail:longint;
kolej:array[1..1000,1..2] of longint;


Procedure dod_kolej(m1,m2,m3:longint);
begin
if (m1>0) and (m1<=8) and (m2>0) and (m2<=8) then
begin
if tab[m1,m2]>m3 then
begin
tab[m1,m2]:=m3;
tail:=tail+1;
kolej[tail,1]:=m1;
kolej[tail,2]:=m2;
end;
end;
end;

Procedure wez_kolej;
begin
head:=head+1;
w1:=kolej[head,1];
w2:=kolej[head,2];
w3:=tab[w1,w2];
end;


Procedure BFS;
begin
while head<>tail do
begin
wez_kolej;

dod_kolej(w1-2,w2-1,w3+1);
dod_kolej(w1-1,w2-2,w3+1);

dod_kolej(w1+2,w2-1,w3+1);
dod_kolej(w1+1,w2-2,w3+1);

dod_kolej(w1-2,w2+1,w3+1);
dod_kolej(w1-1,w2+2,w3+1);

dod_kolej(w1+2,w2+1,w3+1);
dod_kolej(w1+1,w2+2,w3+1);
end;
end;



begin
repeat
readln(c1,zm1,ch,c2,zm2);

d1:=ord(c1)-ord('a')+1;
d2:=ord(c2)-ord('a')+1;
for x:=1 to 8 do for y:=1 to 8 do tab[x,y]:=1000;
tail:=0;
head:=0;
dod_kolej(zm1,d1,0);
BFS;
Writeln('To get from ',c1,zm1,' to ',c2,zm2,' takes ',tab[zm2,d2],' knight moves.');

until eof;
end.

[jhonny_yang]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <io.h>
#include <fcntl.h>

typedef struct{
int x,y;
}node;

int Board[8][8];
node Stack[180];

int main()
{
#ifndef ONLINE_JUDGE
close(0);open("in.txt",O_RDONLY);
close(1);open("out.txt",O_WRONLY|O_CREAT,200);
#endif

int x,y,targetx,targety,counter,iStack,dStack,done,result;
char buff1[10],buff2[10];

while (scanf("%s %s\n",buff1,buff2)==2){
for (y=0;y<8;y++){
for (x=0;x<8;x++){
Board[y][x]=0;
}
}

x=buff1[0]-'a';
y=buff1[1]-'0'-1;
targetx=buff2[0]-'a';
targety=buff2[1]-'0'-1;

counter=0;done=1;
Stack[0].x=x;
Stack[0].y=y;
iStack=1;dStack=0;

while (done){
x=Stack[dStack].x;
y=Stack[dStack++].y;
counter=Board[y][x];

if (x==targetx && y==targety){
result=Board[targety][targetx];
done=0;
}else{
++counter;
if (y-2>=0){
if (x-1>=0){
if (Board[y-2][x-1]==0){
Board[y-2][x-1]=counter;
Stack[iStack].x=x-1;
Stack[iStack++].y=y-2;
}
}
if (x+1<8){
if (Board[y-2][x+1]==0){
Board[y-2][x+1]=counter;
Stack[iStack].x=x+1;
Stack[iStack++].y=y-2;
}
}
}

if (y+2<8){
if (x-1>=0){
if (Board[y+2][x-1]==0){
Board[y+2][x-1]=counter;
Stack[iStack].x=x-1;
Stack[iStack++].y=y+2;
}
}
if (x+1<8){
if (Board[y+2][x+1]==0){
Board[y+2][x+1]=counter;
Stack[iStack].x=x+1;
Stack[iStack++].y=y+2;
}
}
}

if (x-2>=0){
if (y-1>=0){
if (Board[y-1][x-2]==0){
Board[y-1][x-2]=counter;
Stack[iStack].x=x-2;
Stack[iStack++].y=y-1;
}
}
if (y+1<8){
if (Board[y+1][x-2]==0){
Board[y+1][x-2]=counter;
Stack[iStack].x=x-2;
Stack[iStack++].y=y+1;
}
}
}

if (x+2<8){
if (y-1>=0){
if (Board[y-1][x+2]==0){
Board[y-1][x+2]=counter;
Stack[iStack].x=x+2;
Stack[iStack++].y=y-1;
}
}
if (y+1<8){
if (Board[y+1][x+2]==0){
Board[y+1][x+2]=counter;
Stack[iStack].x=x+2;
Stack[iStack++].y=y+1;
}
}
}
}
}

printf("To get from %s to %s takes %d knight moves.\n",buff1,buff2,result);
}

return 0;
}
//@END_OF_SOURCE_CODE

Why WA ?

[jiayaoyu]

[c]
#include <stdio.h>

int graph[64][64];
int result[64][64];
int visited[64];
int len[64];

int dijkstra(int s,int d);
void init()
{
int i,j;
for(i = 0;i<8;i++)
for(j = 0;j<8;j++)
{
if(i+2<8)
{
if(j-1>=0)
graph[8*i+j][8*(i+2)+(j-1)] = 1;
if(j+1<8)
graph[8*i+j][8*(i+2)+(j+1)] = 1;
}
if(i+1<8)
{
if(j-2>=0)
graph[8*i+j][8*(i+1)+(j-2)] = 1;
if(j+2<8)
graph[8*i+j][8*(i+1)+(j+2)] = 1;
}
if(i-2>=0)
{
if(j-1>=0)
graph[8*i+j][8*(i-2)+(j-1)] = 1;
if(j+1<8)
graph[8*i+j][8*(i-2)+(j+1)] = 1;
}
if(i-1>=0)
{
if(j-2>=0)
graph[8*i+j][8*(i-1)+(j-2)] = 1;
if(j+2<8)
graph[8*i+j][8*(i-1)+(j+2)] = 1;
}
}


/* for(i =0;i<64;i++)
for(j = 0;j<64;j++)
result[j] = dijkstra(i,j);*/
}

int dijkstra(int s,int d)
{
int i,j,best,best_j;

visited[s] = 1;

do{
best = 0;
for(i = 0;i<64;i++)
{
if(visited)
for(j = 0;j<64;j++)
{
if(!visited[j]&&graph[j]>0)
{

if(best==0||len+1<best)
{
best = len+1;
best_j = j;
}
}
}
}
if(best>0)
{
visited[best_j] = 1;
len[best_j] = best;
}
}while(best>0);
return len[d];
}





int main(int argc, char *argv[]) {
int i,j,s,d,shortest;
char *rs;
char *rd;

char buff[100];
char tmp[100];
init();
while(gets(tmp)>0)
{
if(strlen(tmp)==0)break;
strcpy(buff,tmp);
rs =(char*) strtok(buff," ");
rd =(char*) strtok(NULL," ");


s = 8*(rs[0]-'a')+rs[1]-'1';
d = 8*(rd[0]-'a')+rd[1]-'1';
for(i = 0;i<64;i++)
{
visited=0;
len=0;
}
if(result[s][d]!=0)
shortest= result[s][d];
else shortest = result[s][d] = dijkstra(s,d);

printf("To get from %s to %s takes %d knight moves.\n",rs,rd,shortest);
tmp[0] = '\0';

}



return 0;
}
[/c]

i've tested all the possible input and all of them are calculated immediately...

[jiayaoyu]

Dijkstra is not very efficient.
I got AC after I switched to dynamic programming.

jhonny_yang,
the code here should give the correct answer as well, so generate all possible input and compare the output of my program with yours. Hope this can help.

[Yarin]

You can also always precalc the the number of jumps based on the distance in x and distance in y. That's just a 64 entry table. There's only one special case to consider - when jumping from a square to the next square in the diagonal (a1->b2, a8->b7, g7->h8 etc). Could be implemented in quite little code too, like this:

main(){char a,b,x,y,m,n,*p="@BBT;9KK2DBT;;KKBBDTKKKMDDTTMMM]";while(scanf("%c%c %c%c\n",&a,&b,&x,&y)>3){m=abs(a-x);n=abs(b-y);printf("To get from %c%c to %c%c takes %d knight moves.\n",a,b,x,y,(6&(a|b))&&(6&(x|y))||m*n-1?p[n*4+m/2]-40>>m%2*3&7:4);}}

249 bytes excluding final line break. Shorter anyone? (yes I was bored )

[qsort]

using floyd-warshall one can write a quite short solution, too

#define f(a) for(a=0;a<64;a++)
main(){int s[64][64],i,j,k,l;f(i)f(j)s[j]=i-j?abs(i%8-j%8)*abs(i/8-j/8)-2?42:1:0;f(j)f(i)f(k){l=s[j]+s[j][k];if(l<s[k])s[k]=l;}while(scanf("%c%d %c%d\n",&i,&j,&k,&l)>3)printf("To get from %c%d to %c%d takes %d knight moves.\n",i,j,k,l,s[i*8+j-777][k*8+l-777]);}

[jhonny_yang]

My output solution is same with your output why i get wrong answer ???

[passwd]

hi,

I'm trying to solve p 439 , but I'm getting WA ! Can someone help me please ??

here is the code in C:

Code: Select all

[c]

#include <stdio.h>
/*#define DEBUG*/
#define NUM 800

int dentro(int l,int c) {
   return (l>=0 && l<8 && c>=0 && c<8);
}

void marca(int v[8][8],int j,int k,int valor) {
   int p,q;
   int l,c;
   l = j-2; c=k-1;
   if(dentro(l,c) && v[l][c] > valor) {
      v[l][c]=valor;
      marca(v,l,c,valor+1);
   }
   l = j-2; c = k + 1;
   if(dentro(l,c) && v[l][c] > valor) {
      v[l][c]=valor;
      marca(v,l,c,valor+1);
   }
   l = j-1; c = k - 2;
   if(dentro(l,c) && v[l][c] > valor) {
      v[l][c]=valor;
      marca(v,l,c,valor+1);
   }
   l = j-1; c = k + 2;
   if(dentro(l,c) && v[l][c] > valor) {
      v[l][c]=valor;
      marca(v,l,c,valor+1);
   }
   l = j+1; c = k - 2;
   if(dentro(l,c) && v[l][c] > valor) {
      v[l][c]=valor;
      marca(v,l,c,valor+1);
   }
   l = j+1; c = k + 2;
   if(dentro(l,c) && v[l][c] > valor) {
      v[l][c]=valor;
      marca(v,l,c,valor+1);
   }
   l = j+2; c = k - 1;
   if(dentro(l,c) && v[l][c] > valor) {
      v[l][c]=valor;
      marca(v,l,c,valor+1);
   }
   l = j+2; c = k + 1;
   if(dentro(l,c) && v[l][c] > valor) {
      v[l][c]=valor;
      marca(v,l,c,valor+1);
   }

      #ifdef DEBUG
        for(p=0;p<8;++p) {
           for(q=0;q<8;++q) {
              printf("%d  ",v[p][q]);
           }
           printf("\n");
        }
     #endif


}

int main() {
  char linha[10];

  while(fgets(linha,9,stdin)!=NULL) {
     int tabela[8][8];
     int i,j;
     for(i=0;i<8;++i) {
        for(j=0;j<8;++j) {
           tabela[i][j]=NUM;
        }
     }
     tabela[linha[1] - '0'][linha[0] - 'a']=0;
     marca(tabela,linha[1] - '0', linha[0] - 'a',1);

     #ifdef DEBUG
        for(i=0;i<8;++i) {
           for(j=0;j<8;++j) {
              printf("%d  ",tabela[i][j]);
           }
           printf("\n");
        }
     #endif

     fprintf(stdout,"To get from %c%c to %c%c takes %d knight moves.\n",linha[0],linha[1],
        linha[3],linha[4],tabela[linha[4] - '0'][linha[3] - 'a']);
  }

  return 0;

}

[/c]

thanks !!

[the LA-Z-BOy]

A square is a string consisting of a letter (a-h) representing the column and a digit (1-8 ) representing the row on the chessboard.

i don't think you considered this, you thought squares should be denoted as a0, a1....a7. but in fact it's not. squares are denoted from a1, a2 .... a8. so you need modification on your code to handle this...
simply from...

Code: Select all

     tabela[linha[1] - '0'][linha[0] - 'a']=0; 
     marca(tabela,linha[1] - '0', linha[0] - 'a',1); 

to...

Code: Select all

     tabela[linha[1] - '1'][linha[0] - 'a']=0; 
     marca(tabela,linha[1] - '1', linha[0] - 'a',1); 

and also modification in the printing function

Code: Select all

fprintf(stdout,"To get from %c%c to %c%c takes %d knight moves.\n",linha[0],linha[1], 
        linha[3],linha[4],tabela[linha[4] - '1'][linha[3] - 'a']);

i tested some inputs that your code satisfied,
Greetings

[Observer]

To solve this problem, you really should use Floyd-Warshall algorithm.

It's easy to implement and quite efficient (Preprocessing + looking up table ).

[titid_gede]

i solved this prob using brute force with prunning. not good, but still AC < 1 sec .

[Amir Faisal]

#include<stdio.h>

#define INF -1


int chessb[8][8];
int cost[8][8];
int queue[65];
int head = 0,tail = 0;
int dr[] = {2,2,-2,-2,1,-1,1,-1};
int dc[] = {1,-1,1,-1,2,2,-2,-2};

void solve(char s1[],char s2[]);
void enqueue(int r,int c);
void dequeue(int &r,int &c);
int row(char ch1);
int column(char ch2);

void main()
{
char s1[3],s2[3],ch;
int r,c,n,i;

for(r=0;r<8;r++)
for(c=0;c<8;c++)
chessb[r][c] = 1;


for( ;(scanf("%s%s", s1, s2))==2;)
{
solve(s1,s2);
}

}

void solve(char s1[],char s2[])
{
int i,j,k,l,r,c,m,nr,nc;
int time=0;

head =0,tail = 0;

for(i=0;i<8;i++)
for(j=0;j<8;j++)
cost[j] = INF;

j=column(s1[0]);
i=row(s1[1])-1;
l=column(s2[0]);
k=row(s2[1])-1;

if(i==k&&j==l)
printf("To get from %s to %s takes 0 knight moves.\n",s1,s2);
else
{
enqueue(i,j);
cost[j]=0;

while(head!=tail)
{
dequeue(r,c);

if(r==k&&c==l)
break;

for(m=0;m<8;m++)
{
nr = r + dr[m];
nc = c + dc[m];


if(cost[nr][nc]==INF&&chessb[nr][nc]==1&&nr<8&&nr>=0&&nc<8&&nc>=0)
{
enqueue(nr,nc);
cost[nr][nc] = cost[r][c] + 1;
time++;
}
}

}
printf("To get from %s to %s takes %d knight moves.\n",s1,s2,cost[l][k]);
}

}

void enqueue(int r,int c)
{
queue[head++] = r*8 + c;
}

void dequeue(int &r,int &c)
{
r = queue[tail]/8;
c = queue[tail]%8;
tail++;
}

int column(char ch1)
{
return ch1-97;
}

int row(char ch2)
{
return ch2-48;
}

[seadoo]

I am using a graph search algorithm to solve this problem, and I am getting WA, but I don't know why. Here are some input and output cases, can anyone try them with a AC program? Thanks...

Input:
a1 e4
a2 a8
a3 g5
b1 c1
b2 b6
b3 c4
b4 h8
b8 h8
c2 c6
c3 h4
c6 f7
d2 f8
d4 e6
d6 h8
e2 e6
e4 e8
f1 g6
f4 f7
g1 h3
g4 g8
h2 h4
h7 h8
h8 h8

Output:
To get from a1 to e4 takes 3 knight moves.
To get from a2 to a8 takes 4 knight moves.
To get from a3 to g5 takes 4 knight moves.
To get from b1 to c1 takes 3 knight moves.
To get from b2 to b6 takes 2 knight moves.
To get from b3 to c4 takes 2 knight moves.
To get from b4 to h8 takes 4 knight moves.
To get from b8 to h8 takes 4 knight moves.
To get from c2 to c6 takes 2 knight moves.
To get from c3 to h4 takes 4 knight moves.
To get from c6 to f7 takes 2 knight moves.
To get from d2 to f8 takes 4 knight moves.
To get from d4 to e6 takes 1 knight moves.
To get from d6 to h8 takes 2 knight moves.
To get from e2 to e6 takes 2 knight moves.
To get from e4 to e8 takes 2 knight moves.
To get from f1 to g6 takes 4 knight moves.
To get from f4 to f7 takes 3 knight moves.
To get from g1 to h3 takes 1 knight moves.
To get from g4 to g8 takes 2 knight moves.
To get from h2 to h4 takes 2 knight moves.
To get from h7 to h8 takes 3 knight moves.
To get from h8 to h8 takes 0 knight moves.

[pavelph]

My AC program get me answers like your.

[seadoo]

Pavelph, thank you for your reply.

I don't know what is wrong with my program, I tested it with many inputs and I really don't know what to do next. Have you any special-case-rule in your code or can you suggest me any other input/output test?