633  A Chess Knight
Moderator: Board moderators

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
633  A Chess Knight
Is any special algorithm to solve this question ?
I use BFS with constraint, that after move of type X is allowed to make moves only Y and Z (X,Y,Z are moves from description > K,B,T) and I got WA a few times ....
So, is possible, that knight moves like KTBKTBKTB or KTKTKTKT ? Or is this just a routine ? Could anyone tell me ?
Best regards
Dominik Michniewski
I use BFS with constraint, that after move of type X is allowed to make moves only Y and Z (X,Y,Z are moves from description > K,B,T) and I got WA a few times ....
So, is possible, that knight moves like KTBKTBKTB or KTKTKTKT ? Or is this just a routine ? Could anyone tell me ?
Best regards
Dominik Michniewski
Last edited by Dominik Michniewski on Tue Mar 30, 2004 10:10 pm, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
Re: 633  A Chess Knight
i think you are right. after making a move X you can make a move either Y or Z and if you make Y next then again you can make a move either X or Z and so on.Dominik Michniewski wrote:after move of type X is allowed to make moves only Y and Z (X,Y,Z are moves from description > K,B,T)
i used bfs too. i stored the move to reach to a particular position and when i make a move from that position, i just checked that i don't make the same move to leave that position.
thanx
sohel

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Maybe you should take a look at my code ?
I use BFS, and I think, that I use BFS correctly .... but I got WA. If you want I send you my code It's long but easy to read program ) (I think)
Regards
DM
I use BFS, and I think, that I use BFS correctly .... but I got WA. If you want I send you my code It's long but easy to read program ) (I think)
Regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
why you got WA?
to Dominik,
maybe u assume that if a cell had been visited the knight won't have to go to that cell anymore...and u place a sign saying that the cell had been visited to prevent the knight from visiting it again(maybe to optimize the BFS)
If so...that's where I think is wrong...since a dynamic knight can not use the same movement it just did...it might be more efficient to use loopback to some cell before reaching the destination...so solutions can be different....
If you think the knight will not go the a same cell more than once...you might be wrong there!!
maybe u assume that if a cell had been visited the knight won't have to go to that cell anymore...and u place a sign saying that the cell had been visited to prevent the knight from visiting it again(maybe to optimize the BFS)
If so...that's where I think is wrong...since a dynamic knight can not use the same movement it just did...it might be more efficient to use loopback to some cell before reaching the destination...so solutions can be different....
If you think the knight will not go the a same cell more than once...you might be wrong there!!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Finally I got Accepted on this problem. I have a few stupid mistakes in code, and one wrong assumption: I think it's true, that we should remember, that from every cell on board we can reach using different last move in the same number of steps
Thanks Nick for pointed me to this
Best regards
DM
Thanks Nick for pointed me to this
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 New poster
 Posts: 1
 Joined: Tue Mar 15, 2005 4:24 pm
HELP
Hey, i have a problem with this program , i want to ask if someone could send me the code or some informations..... thanks...

 Learning poster
 Posts: 74
 Joined: Fri May 08, 2009 5:16 pm
Re: 633  A Chess Knight
getting WA in this prob .pls help
Code: Select all
#include<iostream>
#include<math.h>
#include<queue>
#include<string>
#include<algorithm>
#include<map>
#define INF 900000000
using namespace std;
int color[100][100][4];
int n;
int obs[100][100];
int dis[100][100][4];
int sx,sy,dx,dy;
int inx[]={1,1,1,1,2,2,2,2};
int iny[]={2,2,2,2,1,1,1,1};
int ix[]={2,2,2,2};
int iy[]={2,2,2,2};
struct ss
{
int x,y;
int cost;
int type;
};
queue<ss>Q;
void ini()
{
int i,j,k;
while(!Q.empty()) Q.pop();
for(i=0;i<=2*n;i++)
for(j=0;j<=2*n;j++)
{
obs[i][j]=0;
for(k=0;k<4;k++)
color[i][j][k]=0,dis[i][j][k]=INF;
}
}
void type1(ss s1)
{
int i,j,k,l,x,y;
ss s2;
for(i=0;i<8;i++)
{
x=s1.x+inx[i],y=s1.y+iny[i];
if(x>=1&&x<=2*n&&y>=1&&y<=2*n)
{
if(color[x][y][1]==0&&obs[x][y]==0)
{
dis[x][y][1]=s1.cost+1;
color[x][y][1]=1;
s2.x=x,s2.y=y,s2.cost=s1.cost+1,s2.type=1;
Q.push(s2);
}
}
}
}
void type2(ss s1)
{
int i,j,k,l,x,y;
ss s2;
for(i=0;i<4;i++)
{
x=s1.x+ix[i],y=s1.y+iy[i];
if(x>=1&&x<=2*n&&y>=1&&y<=2*n)
{
if(color[x][y][2]==0&&obs[x][y]==0)
{
dis[x][y][2]=s1.cost+1;
color[x][y][2]=1;
s2.x=x,s2.y=x,s2.cost=s1.cost+1,s2.type=2;
Q.push(s2);
}
}
}
}
void type3(ss s1)
{
int i,j,k,l,x,y;
ss s2;
x=2*ns1.x+1;
y=s1.y;
if(color[x][y][3]==0&&obs[x][y]==0)
{
dis[x][y][3]=s1.cost+1;
color[x][y][3]=1;
s2.x=x,s2.y=y,s2.cost=s1.cost+1,s2.type=3;
Q.push(s2);
}
x=s1.x;
y=2*ns1.y+1;
if(color[x][y][3]==0&&obs[x][y]==0)
{
dis[x][y][3]=s1.cost+1;
color[x][y][3]=1;
s2.x=x,s2.y=y,s2.cost=s1.cost+1,s2.type=3;
Q.push(s2);
}
}
void bfs()
{
int i,j,k,l;
ss s1;
color[sx][sy][1]=1;
dis[sx][sy][1]=0;
color[sx][sy][2]=1;
dis[sx][sy][2]=0;
color[sx][sy][3]=1;
dis[sx][sy][3]=0;
s1.x=sx;
s1.y=sy;
s1.cost=0;
s1.type=0;
type1(s1);
type2(s1);
type3(s1);
while(!Q.empty())
{
s1=Q.front();
Q.pop();
//if(s1.cost<4) cout<<s1.x<<" "<<s1.y<<" "<<s1.cost<<endl;
if(s1.type==1) type2(s1),type3(s1);
if(s1.type==2) type1(s1),type3(s1);
if(s1.type==3) type2(s1),type1(s1);
}
}
int main()
{
int i,j,k,l;
while(scanf("%d",&n)==1&&n)
{
ini();
scanf("%d%d",&sx,&sy);
scanf("%d%d",&dx,&dy);
while(scanf("%d%d",&k,&l)==2)
{
if(!k&&!l) break;
obs[k][l]=1;
}
bfs();
k=dis[dx][dy][1];
if(k>dis[dx][dy][2]) k=dis[dx][dy][2];
if(k>dis[dx][dy][3]) k=dis[dx][dy][3];
if(k==INF) printf("Solution doesn't exist\n");
else printf("Result : %d\n",k);
}
return 0;
}

 Experienced poster
 Posts: 139
 Joined: Wed May 18, 2011 3:04 pm
Re: 633  A Chess Knight
You need to notice the type T movement, if Knight stands (1, 1) at start in a board with size 20*20, It can move to (20, 1) or (1, 20), but not (2,1), (1,2), (4,1), (1, 4), ... remember that the movement is mirror reflection with respect to board and one of axes parrelle to board sides. Secondly, the Knight may enter same cell of board more than once, because you can't take same movement type consecutively.
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.