Here (as a reference) is a solution using Uniform-cost search in c++, compiled with -O2
takes less than a second on a i7 (without optimizations takes 3 secs):
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
struct Node {
size_t i, j; int cost;
Node(size_t i, size_t j, int cost) : i(i), j(j), cost(cost) {}
};
bool operator<(const Node& a, const Node& b) { return b.cost < a.cost; }
bool operator==(const Node& a, const Node& b) { return a.i == b.i && a.j == b.j; }
int main() {
const size_t SIZE = 80;
ifstream fis("matrix.txt");
int matrix[SIZE][SIZE];
char crap;
for (size_t i = 0; i < SIZE; i++)
for (size_t j = 0; j < SIZE; j++) {
fis >> matrix[i][j];
if (j < SIZE - 1) fis >> crap;
}
vector<Node> open;
set<Node> closed;
open.push_back(Node(0, 0, matrix[0][0]));
make_heap(open.begin(), open.end());
while (!open.empty()) {
Node node = open.front();
pop_heap(open.begin(), open.end()); open.pop_back();
if (node.i == SIZE - 1 && node.j == SIZE - 1) {
cout << "solution " << node.cost << endl;
return 0;
}
closed.insert(node);
Node children[] = { Node(node.i + 1, node.j, node.cost + matrix[node.i + 1][node.j]),
Node(node.i, node.j + 1, node.cost + matrix[node.i][node.j + 1]) };
for (int k = 0; k < 2; k++) {
Node child = children[k];
if (!closed.count(child)) {
vector<Node>::iterator elem = find(open.begin(), open.end(), child);
if (elem == open.end()) {
open.push_back(child); push_heap(open.begin(), open.end());
} else if (child.cost < (*elem).cost) {
(*elem).cost = child.cost;
make_heap(open.begin(), open.end());
}
}
}
}
}
This solution would be little slow because it calls make_heap
for element replacement in the open node list which rebuilds the heap in the vector, but shouldn't go to forever land and proves that the problem can be solved with UCS. A suggestion is to debug your solution using the base case given in Project Euler problem statement.