439 - Knight Moves

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by 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
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

439 - Knight Moves

Post by 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
New poster
Posts: 5
Joined: Fri Jun 14, 2002 1:10 am
Location: Lancaster.UK

why do i get TLE???

Post by 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
New poster
Posts: 5
Joined: Fri Jun 14, 2002 1:10 am
Location: Lancaster.UK

AC with D.P

Post by jiayaoyu »

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

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
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by 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
New poster
Posts: 1
Joined: Sun Jan 26, 2003 11:41 pm

floyd-warshall

Post by 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
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

Post by jhonny_yang »

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

passwd
New poster
Posts: 14
Joined: Thu Dec 05, 2002 11:20 pm

439 WA

Post by 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
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by 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
Istiaque Ahmed [the LA-Z-BOy]

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

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

It's easy to implement and quite efficient (Preprocessing + looking up table :P ).
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

i solved this prob using brute force with prunning. not good, but still AC < 1 sec :P.
Kalo mau kaya, buat apa sekolah?

Amir Faisal
New poster
Posts: 4
Joined: Wed Aug 13, 2003 2:47 pm
Location: Bangladesh

439--got output limit exit

Post by 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;
}
I love my mother.

seadoo
New poster
Posts: 12
Joined: Mon Dec 15, 2003 6:16 pm

Post by 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
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

You are right!

Post by pavelph »

My AC program get me answers like your.

seadoo
New poster
Posts: 12
Joined: Mon Dec 15, 2003 6:16 pm

Post by 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?

Post Reply

Return to “Volume 4 (400-499)”