633 - A Chess Knight

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

633 - A Chess Knight

Post by Dominik Michniewski » Mon Apr 07, 2003 7:57 am

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)

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Re: 633 - A Chess Knight

Post by saiqbal » Mon Apr 07, 2003 4:30 pm

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:

Post by Dominik Michniewski » Tue Apr 08, 2003 1:57 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)

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Tue Apr 08, 2003 3:40 pm

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:

Post by Dominik Michniewski » Tue Apr 08, 2003 3:46 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)

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

why you got WA?

Post by Nick » Mon Aug 04, 2003 2:54 am

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:

Post by Larry » Mon Aug 04, 2003 5:03 am

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:

Post by Dominik Michniewski » Tue Mar 30, 2004 10:09 pm

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

Post by Black_Dragon » Tue Mar 15, 2005 4:41 pm

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

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 633 - A Chess Knight

Post by Jehad Uddin » Tue Feb 09, 2010 3:19 pm

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

Post by metaphysis » Fri Jun 02, 2017 1:28 am

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.

Post Reply

Return to “Volume 6 (600-699)”