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

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
Sorry, I don`t know special inputs for this problem. But I can see your code and will try to find mistake. One problem: I know only Pascal
And if your program in another source I can`t check it. But maybe somebode else will help you.

New poster
Posts: 12
Joined: Mon Dec 15, 2003 6:16 pm
Ah, I had an nasty bug in my code, and of all possible input cases (4069), only a few were wrong. And obvious, the judge tested one of them

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

439 WA

novice programmer

abeacco
New poster
Posts: 1
Joined: Sun Mar 05, 2006 1:10 pm

439 Runtime Error

Why do I get RUNTIME ERROR with this code? It works perfectly on my PC and results matches ok....

---------------------------------------------------------------------

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

#define N 8 // num de files i columnes

class SaltsDeCavall {

int ox, oy; // origen
int dx, dy; // desti
int num_salts_minim;
int M[N][N]; // configuracio actual

inline void provar ( int num_salts, int x, int y ) {
if ( x >= 0 && x <= N && y >= 0 && y <= N ) {
if ( x == dx && y == dy ) {
if ( num_salts+1 < num_salts_minim ) num_salts_minim = num_salts+1;
}
else if ( M[x][y] != 1 ) {
M[x][y] = 1;
recursiu(num_salts+1,x,y);
M[x][y] = 0;
}
}
}

void recursiu ( int num_salts, int x, int y ) {
if ( num_salts < num_salts_minim ) {
provar(num_salts,x+2,y-1);
provar(num_salts,x+2,y+1);
provar(num_salts,x+1,y+2);
provar(num_salts,x-1,y+2);
provar(num_salts,x-2,y+1);
provar(num_salts,x-2,y-1);
provar(num_salts,x-1,y-2);
provar(num_salts,x+1,y-2);
}
}

public:

SaltsDeCavall (int ox, int oy, int dx, int dy) {
this->ox = ox;
this->oy = oy;
this->dx = dx;
this->dy = dy;
num_salts_minim = 1000;

M[ox][oy] = 1;
if ( ox == dx && oy == dy ) num_salts_minim = 0;
else recursiu(0,ox,oy);
M[ox][oy] = 0;
}

int NumDeSalts () {
return num_salts_minim;
}

};

int NumSalts(int Sol[][64], int ox, int oy, int dx, int dy) {

int i,j;

i = 8 * ox + oy;
j = 8 * dx + dy;

if ( Sol[j] != -1 ) return Sol[j];
if ( Sol[j] != -1 ) return Sol[j];

else {
SaltsDeCavall s = SaltsDeCavall(ox,oy,dx,dy);
int salts = s.NumDeSalts();

Sol[j] = salts;
Sol[j] = salts;

return salts;
}

}

int main ( ) {

int ox,oy,dx,dy;
char c1[2];
char c2[2];
int n = 1;
int Sol[64][64];
for ( int i = 0; i<64; i++ ) {
for ( int j = 0; j<64; j++) {
Sol[j] = -1;
}
}

int scan = scanf("%s",&c1);

while ( scan =! 0 && scan != EOF )
{
ox = atoi(&c1[1]) - 1;
oy = c1[0] - 'a';
char c3[3];
c3[0] = c1[0];
c3[1] = c1[1];
c3[2] = '\0';

scanf("%s",&c2);
dx = atoi(&c2[1]) - 1;
dy = c2[0] - 'a';

//printf("ox = %d; oy = %d; dx = %d; dy = %d\n",ox,oy,dx,dy);

if ( ox >= 0 && ox < 8 && oy >= 0 && oy < 8 && dx >= 0 && dx < 8 && dy >= 0 && dy < 8 ) {

int salts = NumSalts(Sol,ox,oy,dx,dy);

printf("To get from %s to %s takes %d knight moves.\n",&c3,&c2,salts);
}

scan = scanf("%s",&c1);
}

return 0;
}

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

439 Knight Tour (WA)

I just used BFS..

I am getting WA..

I generated All possible input and saw that my code goes wrong anser
for 4 inputs. They Are

g2 h1
h1 g2
g7 h8
h8 g7
g8 h7
h7 g8

My code produce 2 moves As result. In fact it needs 4 moves.

I am not getting reason Why my BFS will fail for this inputs only..

Some one Pls give me..

my Code

Code: Select all

``````
#include<stdio.h>
#include<string.h>
#include<string>
#include<queue>
#include<iostream>

#define WHITE 1
#define BLACK 3
#define GRAY 4

using namespace std;

int Color[10][10],Move,Size;
int D[10][10];

void BFS(string src, string dest);

void init_color();

int main()
{

string from,to;

//freopen("439.in","r",stdin);
//freopen("439_1.out","w",stdout);

while(cin>>from >> to)
{

BFS(from,to);

cout<<"To get from "<<from<<" to "<<to<<" takes " <<Move<<" knight moves.\n";

}

return 0;
}

void BFS(string src, string dest)
{
int count,i;
string u;
queue<string> Q;

//memset(Color,WHITE,sizeof(Color));
init_color();

Q.push(src);

count = 0;

Color[src[0]-97][src[1] - 48] = GRAY;
D[src[0]-97][src[1] - 48] = 0;

while(!Q.empty())
{
u = Q.front();
Q.pop();

if(u.compare(dest)==0)
{
Move = D[u[0]-97][u[1] - 48] ;

break;
}

for(i=0; i<=Size; i++)
{
{
}
}

Color[u[0]-97][u[1]-48] = BLACK;

}

}

{

char ch;
int no;
int i,idx;
char tmp1[5],tmp[5];

ch = s[0];
no = s[1] - 48;
idx = -1;

for(i=1; i<=2; i++)
{
if(ch - i >='a' && ch - i <= 'z' && ( no - (3-i) ) >0 )
{
tmp1[0] = ch -i;
tmp1[1] = no - (3-i) + 48 ;
tmp1[2] = NULL;
}

if(ch - i >='a' && ch - i <= 'z' && ( no + (3-i) ) <=8 )
{
tmp1[0] = ch -i;
tmp1[1] =  no + (3-i)+48;
tmp1[2] = NULL;

}

if(ch + i >='a' && ch + i <= 'z' && ( no - (3-i) ) >=1 )
{
tmp1[0] = ch +i;
tmp1[1] =  no - (3-i) + 48;
tmp1[2] = NULL;

}

if(ch + i >='a' && ch + i <= 'z' && ( no + (3-i) ) <=8 )
{
tmp1[0] = ch +i;
tmp1[1] =  no + (3-i)+48;
tmp1[2] = NULL;

}

}

Size = idx;
return ;
}

void init_color()
{

int i,j;
for(i=0; i<10; i++)
for(j=0; j<10; j++)
{
Color[i][j] = WHITE;
D[i][j] = 0;
}

return ;

}

``````

moonstruck
New poster
Posts: 3
Joined: Thu Aug 24, 2006 9:20 am

Help me correcting the 439

In my program any input will give the right output for the first time!!!
But then the output does some mysterious behavior. Where the initialize problem could be?

Here’s the code

Code: Select all

``````#include<stdio.h>

const int M=100;

int dr[8]={ -2, -1,  1,  2,  2,  1,  -1, -2};
int dc[8]={  1,  2,  2,  1,  -1, -2, -2, -1};

char str[100],str1[5],str2[5];
int r1,r2,c1,c2;

struct node
{
int name;
int distance;
char color;
}nd[M][M];

class queue
{
public:

int data [M];

queue()
{
}
void init()
{
}
int is_full()
{
if(tail==M)
return 1;
return 0;
}
int is_empty()
{
return 1;
return 0;
}
int insert(int item)
{
if(is_full())
return 0;
data[tail]=item;
tail=tail+1;

return 1;
}
int remove(int &item)
{
if(is_empty())
return 0;

return 1;
}
};

int valid(int r,int c)
{
if( r<0 || c<0 || r>=8 || c>=8)
return(0);
return(1);
}

int BFS(queue q)
{
int nr,nc,i,j,u,v,r,c,k=0;
for(i=1;i<9;i++)
for(j=1; j<9; j++)
{
nd[i][j].name=++k;
nd[i][j].color='w';
nd[i][j].distance=0;
}
nd[r1][c1].color='g';
nd[r1][c1].distance=0;

u = nd[r1][c1].name;
r=r1;
c=c1;
q.insert(u);
while(!q.is_empty())
{
q.remove(u);
for(i=1;i<9;i++)
for(j=1;j<9;j++)
if(nd[i][j].name == u)
{
r=i;
c=j;
}
for(i=0;i<8;i++)
{
nr=r+dr[i];
nc=c+dc[i];
if(valid(nr,nc) && nd[nr][nc].color=='w')
{

nd[nr][nc].color='g';
nd[nr][nc].distance=nd[r][c].distance+1;
v = nd[nr][nc].name;
q.insert(v);
if(nr==r2 && nc==c2)
return nd[nr][nc].distance;

}
}
nd[nr][nc].color='b';

}

}

int main()
{
int dist;
queue q;
//freopen("439.in","r",stdin);
//freopen("439.out","w",stdout);
while(gets(str))
{
sscanf(str,"%s%s",&str1,&str2);
r1=str1[0]-'a'+1;
c1=str1[1]-'0';
r2=str2[0]-'a'+1;
c2=str2[1]-'0';

q.init();
dist = BFS(q);

printf("To get from %s to %s takes %d knight moves.\n",str1,str2,dist);

}
return 0;
}
``````

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

439 - Stack OverFlow

Hi all..
I'm trying to solve this problem.. but when I'm compiling, I get "stack overflow" error..
can anyone help??

here's my code

Code: Select all

``````int move(int x,int y,int distance)
{
if(Board[x][y] != INT_MAX)
return Board[x][y];

if((end.x == x && end.y == y) || x >= 8 || y >= 8 || x < 0 || y < 0)
return Board[x][y] = distance;

int r1,r2,r3,r4,r5,r6,r7,r8;

if(x-2 >= 0)
{
if(y-1 >= 0)
Board[x-2][y-1] = r1 = move(x-2,y-1,distance++);

if(y+1 < 8)
Board[x-2][y+1] = r2 = move(x-2,y+1,distance++);
}

if(x-1 >= 0)
{
if(y-2 >= 0)
Board[x-1][y-2] = r3 = move(x-1,y-2,distance++);
if(y+2 < 8)
Board[x-1][y+2] = r4 = move(x-1,y+2,distance++);
}

if(x+2 < 8)
{
if(y-1 >= 0)
Board[x+2][y-1] = r5 = move(x+2,y-1,distance++);
if(y+1 < 8)
Board[x+2][y+1] = r6 = move(x+2,y+1,distance++);
}

if(x+1 < 8)
{
if(y-2 >= 0)
Board[x+1][y-2] = r7 = move(x+1,y-2,distance++);
if(y+2 < 8)
Board[x+1][y+2] = r8 = move(x+1,y+2,distance++);
}

return Min(r1,r2,r3,r4,r5,r6,r7,r8);
}``````

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

Help???

I sent a post here about this problem but noone replied.. can anyone help??
http://online-judge.uva.es/board/viewtopic.php?t=12546

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:

I m getting wrong on this problem ...I have applied BFS .

Code: Select all

``````#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

using namespace std;

struct node
{
int x,y;
int cost;
};

class knight
{

public:
int input()
{
string s1,s2;
while(cin)
{
cin>>s1>>s2;
int z=bfs(s1,s2);
cout<<"To get from "<<s1<<" to "<<s2<<" takes "<<z<<" knight moves.\n";
}
}

int bfs(string s1,string s2)
{
int a,b1,c1,d1;
a=s1[0]-'a';
b1=s1[1]-'0'-1;
c1=s2[0]-'a';
d1=s2[1]-'0'-1;
//cout<<a<<" "<<b1<<" "<<c1<<" "<<d1<<"\n";

bool b[8][8];
for(int i=0;i<8;i++) for(int j=0;j<8;j++) b[i][j]=true;

node p;
p.x=a;p.y=b1;p.cost=0;

queue<node> q;
q.push(p);

while(q.size()!=0)
{
node n=q.front();
q.pop();
int x=n.x;
int y=n.y;
int c=n.cost;

//cout<<x<<" "<<y<<" "<<c<<"\n";

if(x==c1 && y==d1)
return c;

if(x-2>=0)
{
if(y-1>=0 && b[x-2][y-1])
{
b[x-2][y-1]=false;
node t={x-2,y-1,c+1};
q.push(t);
}
if(y+1<8 && b[x-2][y+1])
{
b[x-2][y+1]=false;
node t={x-2,y+1,c+1};
q.push(t);
}
}

if(x+2<8)
{
if(y-1>=0  && b[x+2][y-1])
{
b[x+2][y-1]=false;
node t={x+2,y-1,c+1};
q.push(t);
}
if(y+1<8  && b[x+2][y+1])
{
b[x+2][y+1]=false;
node t={x+2,y+1,c+1};
q.push(t);
}
}

if(y+2<8)
{
if(x-1>=0  && b[x-1][y+2])
{
b[x-1][y+2]=false;
node t={x-1,y+2,c+1};
q.push(t);
}
if(x+1<8 && b[x+1][y+2])
{
b[x+1][y+2]=false;
node t={x+1,y+2,c+1};
q.push(t);
}
}

if(y-2>=0)
{
if(x-1>=0 && b[x-1][y-2])
{
b[x-1][y-2]=false;
node t={x-1,y-2,c+1};
q.push(t);
}
if(x+1<8  && b[x+1][y-2])
{
b[x+1][y-2]=false;
node t={x+1,y-2,c+1};
q.push(t);
}
}
}
return -1;
}
};
int main()
{
knight k;
k.input();
return 0;
}

``````
Can anybody help me to find out the error !!!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Replace

Code: Select all

``````            while(cin)
{
cin>>s1>>s2;``````
with

Code: Select all

``````            while(cin>>s1>>s2)
{
``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am
No runtime error now
bfs should work well now, yet another bug occur....
Last edited by kn on Sat Jun 09, 2007 12:20 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the case.

Input:

Code: Select all

``a2 b1``
Output:

Code: Select all

``To get from a2 to b1 takes 2 knight moves.``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am
Jan wrote:Try the case.

Input:

Code: Select all

``a2 b1``
Output:

Code: Select all

``To get from a2 to b1 takes 2 knight moves.``
Hope it helps.
finally I figured out my silly bug...THX Jan, again
but after I changed it...still WA...

Code: Select all

``````ACed...
Two silly bugs...concerning indexes...sigh=.=
``````
Last edited by kn on Sun Jun 10, 2007 7:40 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases.

Input:

Code: Select all

``````a2 b8
a2 h4
a2 h3
a2 d2``````
Output:

Code: Select all

``````To get from a2 to b8 takes 3 knight moves.
To get from a2 to h4 takes 5 knight moves.
To get from a2 to h3 takes 4 knight moves.
To get from a2 to d2 takes 3 knight moves.``````
Hope these help.
Ami ekhono shopno dekhi...
HomePage

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am
Jan wrote:Try the cases.

Input:

Code: Select all

``````a2 b8
a2 h4
a2 h3
a2 d2``````
Output:

Code: Select all

``````To get from a2 to b8 takes 3 knight moves.
To get from a2 to h4 takes 5 knight moves.
To get from a2 to h3 takes 4 knight moves.
To get from a2 to d2 takes 3 knight moves.``````
Hope these help.
AC

Sigh...always get confused by the indexes
Next time I will be more more more careful~

Thx again for your test cases, Jan