## 439 - Knight Moves

Moderator: Board moderators

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

I have no idea why my program always gives WA.

When I am testing it everything is OK.

Program p439;
VAR
ch,c1,c2:char;
zm1,zm2:longint;
wynik:longint;
tab:array[1..8,1..8] of 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
w3:=tab[w1,w2];
end;

Procedure BFS;
begin
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

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;
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

#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???

[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

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

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
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

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
Contact:
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
To solve this problem, you really should use Floyd-Warshall algorithm.

It's easy to implement and quite efficient (Preprocessing + looking up table ).
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
i solved this prob using brute force with prunning. not good, but still AC < 1 sec .
Kalo mau kaya, buat apa sekolah?

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

### 439--got output limit exit

#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;

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;

{
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)
{
}

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.

New poster
Posts: 12
Joined: Mon Dec 15, 2003 6:16 pm
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!

My AC program get me answers like your.

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