hi i'm working on little project requires me build matrix in java resembles chess board. i'm supposed knight point another(in way knight moves). need find shortest way there in end.
my problem is, can't connect edges point. can find out if vertex valid move can't seem find way create nodes point. example,
0 xxxxx
1 xxxox
2 xxxxx
3 xxkxx
4 xxxxx
5 xxxxx
i need create nodes connect k o find out shortest distance later. ps. i'll okay hints of how there or tips. don't need exact code. thank much! know it's bad representation of matrix there spare me critique please
a classic breadth-first-search simplest approach:
class location { int x; int y; list<location> adjacent() { // todo return list of locations reachable in single step } } list<location> findshortestpath(location start, location destination) { location[][] previous = new location[8][8]; deque<location> queue = new arraydeque<>(); queue.add(start); { location loc = queue.poll(); (location n : loc.neighbors()) { if (previous[n.x][n.y] == null) { previous[n.x][n.y] = loc; queue.add(n); if (n.x == destination.x && n.y == destination.y) { // we've found way, let's reconstruct list of steps list<location> path = new arraylist<>(); (location l = n; l != start; l = previous[l.x][l.y]) { path.add(l); } path.reverse(); return path; } } } } while (!queue.isempty()); return null; // no path exists } this code enumerates paths start location. therefore, if there path destination, find it. in addition, because paths enumerated in order or ascending length, first such path shortest one.
Comments
Post a Comment