JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Introduction to graphs and their data structures shortest path algo in java
 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 que = new LinkedList(); 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; }}
 Forums Tutorial Discussions Introduction to graphs and their data structures shortest path algo in java Previous Thread  |  Next Thread