Page 1 of 1
Graph problem
Posted: Mon Jul 17, 2006 12:43 am
by 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
Posted: Mon Jul 17, 2006 1:03 am
by 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....
Posted: Mon Jul 17, 2006 5:32 am
by 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;
}
Posted: Mon Jul 17, 2006 6:02 am
by 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).
Posted: Mon Jul 17, 2006 7:43 pm
by ayon
this problem is exactly like 439 - knight moves, right?
Posted: Tue Jul 18, 2006 2:24 am
by 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
Take it easy
Posted: Tue Jul 18, 2006 11:55 am
by 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
Posted: Tue Jul 18, 2006 12:16 pm
by ayon
as there exists only 64 nodes, floyd-warshall can be applied very easily
Posted: Wed Jul 19, 2006 4:06 am
by 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.
Posted: Wed Jul 19, 2006 6:04 am
by 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....
Posted: Wed Jul 19, 2006 8:02 am
by Tanu
Check private massage
Posted: Wed Jul 19, 2006 1:13 pm
by cypressx
Don't worry dude !
If you still have problems after Tanu's private message ask here..
Posted: Fri Jul 28, 2006 10:31 am
by gijs
Isn't Dijkstra's algorithm the fastest one for shortest-path problems?