JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
shortest path algo in java | Reply
"Bob has become lost in his neighborhood. He needs to get from his current position back to his home. Bob's neighborhood is a 2 dimensional grid, that starts at (0, 0) and (width - 1, height - 1). There are empty spaces upon which bob can walk with no difficulty, and houses, which Bob cannot pass through. Bob may only move horizontally or vertically by one square at a time.

Bob's initial position will be represented by a 'B' and the house location will be represented by an 'H'. Empty squares on the grid are represented by '.' and houses are represented by 'X'. Find the minimum number of steps it takes Bob to get back home, but if it is not possible for Bob to return home, return -1.

An example of a neighborhood of width 7 and height 5:

...X..B
.X.X.XX
.H.....
...X...
.....X."
Re: shortest path algo in java (response to post by akrjain151089) | Reply
import java.util.*;
public class Game2{
public class Pixel{
int x,y;
boolean marked;
long path;
public Pixel(int x,int y){
this.x = x;
this.y = y;
this.marked = false;
this.path = 0;
}
}
public long findHome(String B,String H,String[] houses){
Pixel grid[][] = new Pixel[51][51];
for(int i=0;i<grid.length;i++)
for(int j=0;j<grid[i].length;j++)
grid[i][j] = new Pixel(i,j);
StringTokenizer st;
int ch1,ch2;
for(String house : houses){
st = new StringTokenizer(house,",");
ch1 = Integer.parseInt(st.nextToken());
ch2 = Integer.parseInt(st.nextToken());
grid[ch1][ch2].marked = true;
}
Queue><Pixel> que = new LinkedList<Pixel>();
int endx,endy,stx,sty;
st = new StringTokenizer(H,",");
endx = Integer.parseInt(st.nextToken());
endy = Integer.parseInt(st.nextToken());
st = new StringTokenizer(B,",");
stx = Integer.parseInt(st.nextToken());
sty = Integer.parseInt(st.nextToken());
grid[stx][sty].marked = true;
que.add(grid[stx][sty]);
Pixel top,next;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int x,y;
while(!que.isEmpty()){
top = que.poll();
for(int i=0;i<4;i++){
x = top.x+dx[i];
y = top.y+dy[i];
if(x<0||x>50||y<0||y>50||grid[x][y].marked)
continue;
if((x==endx)&&(y==endy))
return top.path+1;
grid[x][y].marked=true;
next=grid[x][y];
next.path=(top.path+1);
que.add(next);
}
}
return -1;
}
}
RSS