## Graph problem

**Moderator:** Board moderators

### 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

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

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;
}
```

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

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

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);
}
}
}
```

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

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]

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

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

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