439 - Knight Moves

[pavelph]

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.

[seadoo]

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]

Getting WA. Please help me with some critical inputs

[abeacco]

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]

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


string Adj[10];


void BFS(string src, string dest);

void generate_adjacent(string s);

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

		generate_adjacent(u);

		for(i=0; i<=Size; i++)
		{
			if( Color[Adj[i][0]-97][Adj[i][1]-48] == WHITE )
			{				
				Q.push(Adj[i]);
				D[Adj[i][0]-97][Adj[i][1]-48] = D[u[0]-97][u[1]-48] + 1;
				Color[Adj[i][0]-97][Adj[i][1]-48] = GRAY;			
			}		
		}
		

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


	
	
	}
	


}



void generate_adjacent(string s)
{
	
	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;
			Adj[++idx] = tmp1;
		}

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

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


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

	
	}

	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]

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];
	int head,tail;

		queue()
		{
			head=tail=0;
		}
		void init()
		{
			head=tail=0;
		}
		int is_full()
		{
			if(tail==M)
				return 1;
			return 0;
		}
		int is_empty()
		{
			if(head==tail)
				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;
			item=data[head];
			head=head+1;
			
			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]

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]

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]

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]

Replace

Code: Select all

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

with

Code: Select all

            while(cin>>s1>>s2) 
            { 
                    

Hope it helps.

[kn]

No runtime error now
bfs should work well now, yet another bug occur....

[Jan]

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.

[kn]

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

[Jan]

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.

[kn]

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