633 - A Chess Knight

[Dominik Michniewski]

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

[saiqbal]

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]

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

[saiqbal]

sure, you can email me the code.

-sohel

[Dominik Michniewski]

I send you my code via PM. Please check it ...

DM

[Nick]

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]

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

[Dominik Michniewski]

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

[Black_Dragon]

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

[Jehad Uddin]

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]

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.