633 - A Chess Knight

Moderator: Board moderators

Dominik Michniewski
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
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)

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:

Re: 633 - A Chess Knight

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

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

Dominik Michniewski
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
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)

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:
sure, you can email me the code.

-sohel

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I send you my code via PM. Please check it ...

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)

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
So instead of remembering just the board, you also remember the board and the last move taken?

Dominik Michniewski
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
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)

Black_Dragon
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*n-s1.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*n-s1.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;
}

``````

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