35 lines
1.1 KiB
C++
35 lines
1.1 KiB
C++
#include "Grid.h"
|
|
#include "algorithms/BinaryTree.h"
|
|
#include "algorithms/Sidewinder.h"
|
|
|
|
// Find the longest path through the maze
|
|
// 1. Run Dijkstra's algorithm to find the farthest cell from the start
|
|
// 2. Run Dijkstra's algorithm again to find the farthest cell from the cell found in step 1
|
|
// 3. The path between the two cells is the longest path through the maze
|
|
// NOTE: This is not the most efficient way to find the longest path through a maze,
|
|
// it would be more efficient to think of the maze as a tree and find the width/diameter
|
|
// of the tree using a depth first search.
|
|
int main() {
|
|
// build the grid & set it up
|
|
DistanceGrid grid(10, 10);
|
|
Sidewinder::on(grid);
|
|
|
|
auto& start = grid.getCellRef(0, 0);
|
|
grid.setStart(start);
|
|
|
|
// run Dijkstra's algorithm to find farthest cell
|
|
auto distances = start.distances();
|
|
auto [new_start, distance] = distances.max();
|
|
|
|
// run Dijkstra's algorithm again
|
|
auto new_distances = new_start.distances();
|
|
auto [goal, distance2] = new_distances.max();
|
|
|
|
// find the path
|
|
grid.distances = new_distances.pathTo(goal);
|
|
|
|
std::cout << grid << std::endl;
|
|
}
|
|
|
|
|