Graph problem

[bruk]

I don't know if it is exactly a graph problem, maybe it could be solved in another way...
the problem is, if you have a chess board with a Knight, I need to know (in the fastest way) the short distance to get to another position of the board with this Knight...
(The knight can only makes 8 moves, moving 1 row and 2 cols in any direction or 2 rows and 1 col in any direction)
I hope someone can help me

[cypressx]

Do a bfs from the startx,starty , generate all the possible next positions and if they are not visited enqueue them and so on , keep the distance to D[x][y]. when you pop the position you are interested in stop the bfs and output it's distance....

[bruk]

thanks a lot for your help!! I really appreciate it.
That is something I was trying to do...but I don't know how to make it
Here is my best try...but it doesn't work

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MIN(a,b) a<b?a:b
int R,C;            //rows and cols
bool used[30][30];

int MIN4(int a, int b, int c, int d){
    if(a<b && a<c && a<d) return a;
    if(b<a && b<c && b<d) return b;
    if(c<b && c<a && c<d) return c;
    else return d;
}

int MIN8(int a, int b, int c, int d, int e, int f, int g, int h){
    return MIN4(MIN(a,b),MIN(c,d),MIN(e,f),MIN(g,h));
}

int calc(int x, int y, int endx, int endy){
    if(x==endx && y==endy) return 0;//if I get to this position, return dist = 0
    int dist[9]={10000,10000,10000,10000,10000,10000,10000,10000,10000};
    if(x+2<=R){
        if(y+1<=C){
          if(!used[x+2][y+1]){
              used[x+2][y+1]=true; 
              dist[1]=1 + calc(x+2,y+1,endx,endy);
              used[x+2][y+1]=false;
          }
        }
        if(y-1>=1){
          if(!used[x+2][y-1]){
              used[x+2][y-1]=true;
              dist[2]=1 + calc(x+2,y-1,endx,endy);
              used[x+2][y-1]=false;
          }
        }
    }
    
    if(x-2>=1){
        if(y+1<=C){
          if(!used[x-2][y+1]){
              used[x-2][y+1]=true;
              dist[3]=1 + calc(x-2,y+1,endx,endy);
              used[x-2][y+1]=false;
          }
        }
        if(y-1>=1){
          if(!used[x+2][y-1]){
              used[x+2][y-1]=true;
              dist[4]=1 + calc(x-2,y-1,endx,endy);
              used[x+2][y-1]=false;
          }
        }
    }

    if(x+1<=R){
        if(y+2<=C){
          if(!used[x+1][y+2]){
              used[x+1][y+2]=true;
              dist[5]=1 + calc(x+1,y+2,endx,endy);
              used[x+1][y+2]=false;
          }                   
        }
        if(y-2>=1){
          if(!used[x+1][y-2]){
              used[x+1][y-2]=true;
              dist[6]=1 + calc(x+1,y-2,endx,endy);
              used[x+1][y-2]=false;
          }                                      
        }
    }


    if(x-1>=1){
        if(y+2<=C){
          if(!used[x-1][y+2]){
              used[x-1][y+2]=true;
              dist[7]=1 + calc(x-1,y+2,endx,endy);
              used[x-1][y+2]=false;
          }                   
        }
        if(y-2>=1){
          if(!used[x-1][y-2]){
              used[x-1][y-2]=true;
              dist[8]=1 + calc(x-1,y-2,endx,endy);
              used[x-1][y-2]=false;
          }                   
        }
    }
    return MIN8(dist[1],dist[2],dist[3],dist[4],dist[5],dist[6],dist[7],dist[8]);
}

int main(){
    int D[20][20];
    int startx,starty,endx,endy,i,j;
    scanf("%d %d",&R,&C); //Number of Rows and Cols
    for(i=1;i<=R;i++)
      for(j=1;j<=C;j++)
        used[i][j]=false;

    scanf("%d %d %d %d",&startx,&starty,&endx,&endy);
    //calculate dist from position (startx,starty) to (endx,endy)
    used[startx][starty]=true;
    //this position have been used (is where the Knight starts)
    int sol=calc(startx,starty,endx,endy);
    printf("%d\n",sol);    
    system("PAUSE");
    return 0;
}

[Observer]

Hi bruk,

You code is NOT doing bfs.. Note that your array "int D[20][20]" is never used in your program.

Also, your function MIN4 isn't quite correct (try MIN4(1, 1, 10000, 10000) for instance).

[ayon]

this problem is exactly like 439 - knight moves, right?

[bruk]

THANKS!!!!!!
ok...I changed my code:


here it is:

Code: Select all

void calc(int stx,int sty,int x, int y, int costKnight[27][42][27][42],int dist){
       int r,c;
       r=x+2;
       if(r<=R){
        c=y+1;
        if(c<=C && costKnight[stx][sty][r][c]>dist){
             costKnight[stx][sty][r][c]=dist;
             calc(stx,sty,r,c,costKnight,dist+1);
        }
        c=y-1;
        if(c>=1 && costKnight[stx][sty][r][c]>dist){
             costKnight[stx][sty][r][c]=dist;                
             calc(stx,sty,r,c,costKnight,dist+1);
        }
       }
    
    r=x-2; 
    if(r>=1){
        c=y+1;
        if(c<=C && costKnight[stx][sty][r][c]>dist){
             costKnight[stx][sty][r][c]=dist;
             calc(stx,sty,r,c,costKnight,dist+1);
        }
        c=y-1;   
        if(c>=1 && costKnight[stx][sty][r][c]>dist){
             costKnight[stx][sty][r][c]=dist;
             calc(stx,sty,r,c,costKnight,dist+1);
        }
    }
    
    
    r=x+1;
    if(r<=R){
        c=y+2;
        if(c<=C && costKnight[stx][sty][r][c]>dist){
             costKnight[stx][sty][r][c]=dist;
             calc(stx,sty,r,c,costKnight,dist+1);
        }
        c=y-2;
        if(c>=1 && costKnight[stx][sty][r][c]>dist){
             costKnight[stx][sty][r][c]=dist;
             calc(stx,sty,r,c,costKnight,dist+1);
        }
    }

    r=x-1;
    if(r>=1){
        c=y+2;
        if(c<=C && costKnight[stx][sty][r][c]>dist){
             costKnight[stx][sty][r][c]=dist;
             calc(stx,sty,r,c,costKnight,dist+1);
        }
        c=y-2;
        if(c>=1 && costKnight[stx][sty][r][c]>dist){
             costKnight[stx][sty][r][c]=dist;
             calc(stx,sty,r,c,costKnight,dist+1);
        }
    }
}

Here stx and sty marks which matrix marks and x and y marks position. (stx and sty marks that I was getting distances from a knight starting at stx,sty)
Now it works, but it is too slow for what I need to do...
I need to get the distance from every position of the board to every other position...I think I must use some dynamic, but I can't see where

I didn't know problem 439, the problem I was trying to solve is from Usaco train, (CAMELOT problem)
....
if someone knows how to make it faster, it would help me a lot...
I have stay days and days with this problem and I can't solve it

[Tanu]

439 was my first try in bfs....
Many solvers solved it in 0.016 sec but it is possible to make the time faster...
Think it easily as a simmetric matrix....
if u can go from board[a] to board[c][d] in x step then possibilities:
1. board[c][d] to board[a] will take the same step.
2. I think board[n-a][n-b] to board[n-c][n-d] will take the same time(for nXn board).
It will have to calculate 1/4 calculation of the thinked calculation...
Try it,if works than send private msg...
Thanx in advance....
...Tanu

[ayon]

as there exists only 64 nodes, floyd-warshall can be applied very easily

[cypressx]

I think you actually got the right algorithm for Camelot , but try to do it with bfs , because this recursion does many stack calls. And posting the whole matrix and so many variables .. only fills the stack , I don't know how much memory does it need. And the bfs finds the optimal way when you visit a state , whether in the recursion a.k.a dfs you optimize everytime you visit a state with less moves .. so it's so much slower.

[bruk]

Tanu:
I get the idea, but I am still thinking how to adapt my algorithm to use previous information that I have calculated. I really don't know how.

ayon:
You are right, but in the problem that I am actually trying to solve (CAMELOT) the board can be of (25x40) and I have to calculate for all the board all the distances from every position to every other position....so I think floyd it would be a little slow for this particular case

cypressx:
I don't understand how to change my implementation to a bfs, I really don't understand right your idea...

plz, sorry for my ignorance , I am really stuck with this problem and I am getting crazy....I think it has passed more than a week since I was trying to solve this....day after day after day
I really appreciate your help guys!! it's so useful to me....
thanks a lot for the help you already give me....

[Tanu]

Check private massage

[cypressx]

Don't worry dude !
If you still have problems after Tanu's private message ask here..

[gijs]

Isn't Dijkstra's algorithm the fastest one for shortest-path problems?