## 633 - A Chess Knight

Moderator: Board moderators

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

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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

saiqbal
New poster

Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm

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

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

sure, you can email me the code.

-sohel

saiqbal
New poster

Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm

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

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### 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!!
Nick
Learning poster

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

So instead of remembering just the board, you also remember the board and the last move taken?
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

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

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### HELP

Hey, i have a problem with this program , i want to ask if someone could send me the code or some informations..... thanks...
Black_Dragon
New poster

Posts: 1
Joined: Tue Mar 15, 2005 4:24 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 900000000using 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;}`