Another constraint to the bridge exercise was to give the length of the bridge found. I had not looked into this as this has very little interest (it would be more relevant if we actually were looking for the shortest one...), but to be complete, here is the solution with the length. The idea is to keep track of the distance of a point. Candidates are considered 1 unit further than the current node  so by iteration, it is easy to count the length.
Again, this doesn't give the shortest path, but just says whether a bridge can be built or not. More on this later.
#include <list> #include <cmath> #include <string> #include <iostream> #include <cassert> #include <cstdlib> #include <algorithm> const int X_MAX = 6; const int Y_MAX = 6; class point { public: int x; int y; int distance; point() : x(0), y(0) { } point(int x, int y) : x(x), y(y), distance(0) { } point(int x, int y, int d) : x(x), y(y), distance(d) { } ~point() { } void print() const { std::cout << "(" << x << "," << y << ")" << std::endl; } bool operator==(point p) const { return x == p.x && y == p.y; } bool is_neighbour(point p) { return ((std::abs((double) x  p.x) == 1 && y == p.y)  (std::abs((double) y  p.y) == 1 && x == p.x)); } point west() { assert((y  1) > 0); return point(x, y  1, distance+1); } point east() { assert(y + 1 < Y_MAX); return point(x, y + 1, distance+1); } point north() { assert(x  1 > 0); return point(x  1, y, distance+1); } point south() { assert(x + 1 < X_MAX); return point(x + 1, y, distance+1); } }; static std::list<point> visited; static int length; bool is_point_visited(point p) { std::list<point>::iterator result = std::find(visited.begin(), visited.end(), p); return *result == p; } // Adjust coordinates to have (0,0) at the bottom lefthand corner. char get_char(point p, std::string* map) { return map[Y_MAX  p.y  1][p.x]; } // Will be useful for the terminating condition. bool has_arrived(point current, point end) { return current.is_neighbour(end); } std::list<point> find_candidates(point current, std::string* map) { std::list<point> candidates; // West if (current.y  1 > 0 && get_char(current.west(), map) == '0') { if (!is_point_visited(current.west())) candidates.push_back(current.west()); } // East if (current.y + 1 < Y_MAX && get_char(current.east(), map) == '0') { if (!is_point_visited(current.east())) candidates.push_back(current.east()); } // North if (current.x  1 > 0 && get_char(current.north(), map) == '0') { if (!is_point_visited(current.north())) candidates.push_back(current.north()); } // South if (current.x + 1 < X_MAX && get_char(current.south(), map) == '0') { if (!is_point_visited(current.south())) candidates.push_back(current.south()); } return candidates; } bool iter(point current, point end, std::string* map) { visited.push_front(current); if (has_arrived(current, end)) { length = current.distance; return true; } std::list<point> candidates = find_candidates(current, map); if (candidates.empty()) { return false; } else { while (!candidates.empty()) { if (iter(candidates.front(), end, map)) { return true; } else { candidates.pop_front(); } } return false; } } int main() { std::string map[] = {"1000020", "0100113", "3003000", "2033000", "2003111", "2000010"}; point start(0, 0); point end(5, 5); length = 1; if (iter(start, end, map)) { std::cout << "indeed" << std::endl; std::cout << "bridge is " << length << " long." << std::endl; } else { std::cout << "nope" << std::endl; } std::cout << "visited " << visited.size() << " nodes." << std::endl; }
Again, this doesn't give the shortest path, but just says whether a bridge can be built or not. More on this later.
1 Comments On This Entry
Page 1 of 1
diego_pmc
07 November 2009  05:25 AMQuote
I had not looked into this as this has very little interest (it would be more relevant if we actually were looking for the shortest one...)
Finding the shortest possible bridge is actually one of the requirements of the full exercise. I said previously, finding whether or not it is possible to build a bridge between two points is only part of the full exercise. The paper sheet with the instructions is in Romanian and it's quite a lot to translate so I only mentioned the details relevant to this particular algorithm. Besides, in order to find the shortest bridge you must first calculate the length of all bridges, right?
There are a few other things you are asked to do in that exercise. For example you have to find out how many islands* each country has on the map. I only mentioned the bridge part because that's the hardest one.
*Two elements belong to the same island if they are of the same value and they are neighbors, or if they are of the same value and if you can get from one element to the any other through neighbor elements.
1 isle 2 isles 3 isles 0001 2020 0030 0011 0220 0300 0110 0000 3000
Page 1 of 1
My Blog Links
Search My Blog
Recent Entries

Pathfinding: Walk on the Bridge (II)
on Nov 06 2009 10:46 AM
Tags
Recent Comments
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)