Graph problem

Moderator: Board moderators

bruk
New poster
Posts: 5
Joined: Mon Jul 17, 2006 12:39 am

Graph problem

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
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm
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
New poster
Posts: 5
Joined: Mon Jul 17, 2006 12:39 am
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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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).
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
this problem is exactly like 439 - knight moves, right?
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

bruk
New poster
Posts: 5
Joined: Mon Jul 17, 2006 12:39 am
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
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

Take it easy

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...
...Tanu

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
as there exists only 64 nodes, floyd-warshall can be applied very easily
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm
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
New poster
Posts: 5
Joined: Mon Jul 17, 2006 12:39 am
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....

Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars
Check private massage

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm
Don't worry dude !
If you still have problems after Tanu's private message ask here..

gijs
New poster
Posts: 3
Joined: Tue Feb 21, 2006 12:40 pm
Isn't Dijkstra's algorithm the fastest one for shortest-path problems?