Page 2 of 3

Posted: Fri Jan 02, 2004 4:01 pm
by 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.

Posted: Fri Jan 02, 2004 8:07 pm
by 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 :)

439 WA

Posted: Mon Jun 14, 2004 4:27 am
by samueljj
Getting WA. Please help me with some critical inputs :cry:

439 Runtime Error

Posted: Sun Mar 05, 2006 1:13 pm
by 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;
}

439 Knight Tour (WA)

Posted: Wed Jul 26, 2006 7:19 pm
by 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 ;

}


Help me correcting the 439

Posted: Thu Aug 24, 2006 10:56 am
by 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;
}

439 - Stack OverFlow

Posted: Thu Oct 26, 2006 11:29 am
by 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);
}

Help???

Posted: Thu Oct 26, 2006 12:33 pm
by 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

439 Wrong Answer

Posted: Sun Dec 31, 2006 8:04 pm
by 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 !!!

Posted: Thu Jan 04, 2007 2:32 pm
by Jan
Replace

Code: Select all

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

Code: Select all

            while(cin>>s1>>s2) 
            { 
                    
Hope it helps.

Posted: Thu Jun 07, 2007 10:51 pm
by kn
No runtime error now
bfs should work well now, yet another bug occur....

Posted: Sat Jun 09, 2007 1:12 am
by 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.

Posted: Sat Jun 09, 2007 12:20 pm
by kn
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=.=

Posted: Sat Jun 09, 2007 5:54 pm
by 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.

Posted: Sun Jun 10, 2007 7:39 pm
by kn
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