Search⌘ K
Home
Courses
Mazes for Programmers

Solution: Coloring Cells by Shortest Distance

Explore the process of coloring maze cells by calculating shortest distances from a starting point using Dijkstra's algorithm. This lesson helps you understand how to implement and visualize distance calculations across maze grids, enhancing your ability to solve and analyze maze structures algorithmically.

We'll cover the following...

Solution

Let's run the code given below to compare your output image.

C++
require 'distances'
class Cell
  attr_reader :row, :column
  attr_accessor :north, :south, :east, :west
  def initialize(row, column)
    @row, @column = row, column
    @links = {}
  end
  def link(cell, bidi=true)
    @links[cell] = true
    cell.link(self, false) if bidi
    self
  end
  def unlink(cell, bidi=true)
    @links.delete(cell)
    cell.unlink(self, false) if bidi
    self
  end
  def links
    @links.keys
  end
  def linked?(cell)
    @links.key?(cell)
  end
  def neighbors
    list = []
    list << north if north
    list << south if south
    list << east  if east
    list << west  if west
    list
  end
  def distances(from: [self])
    # work your magic here!
    distances = Distances.new(from.first) 
    from.each { |cell| distances[cell] = 0 }
    frontier = [ *from ]
    while frontier.any? 
      new_frontier = [] 
      frontier.each do |cell| 
        cell.links.each do |linked| 
          next if distances[linked] 
          distances[linked] = distances[cell] + 1 
          new_frontier << linked 
        end
      end
      frontier = new_frontier 
    end
    distances
  end
end

Code explanation

Line 41: The method takes an optional parameter, from—representing the starting cell for which we want to calculate the distance—which defaults to an array containing the current object self ...