the previous example* Write a program Maze.java that takes a command line parame

Question

the previous example*

Write a program Maze.java that takes a command line parameter N, and generates a random N-by-N perfect maze. A maze is perfect if it has exactly one path between every pair of points in the maze, i.e., no inaccessible locations, no cycles, and no open spaces. Here's a nice algorithm to generate such mazes. Consider an N-by-N grid of cells, each of which initially has a wall between it and its four neighboring cells. For each cell (x, y), maintain a variable north[x][y] that is true if there is wall separating (x, y) and (x, y + 1). We have analogous variables east[x][y], south[x][y], and west[x][y] for the corresponding walls. Note that if there is a wall to the north of (x, y) then north[x][y] = south[x][y+1] = true. Construct the maze by knocking down some of the walls as follows:

Start at the lower level cell (1, 1).

Find a neighbor at random that you haven't yet been to.

If you find one, move there, knocking down the wall. If you don't find one, go back to the previous cell.

Repeat steps ii. and iii. until you've been to every cell in the grid.

Hint: maintain an (N+2)-by-(N+2) grid of cells to avoid tedious special cases.

*end of pervious example*

Given an N-by-N maze (like the one created in the previous exercise), write a program to find a path from the start cell (1, 1) to the finish cell (N, N), if it exists. To find a solution to the maze, run the following algorithm, starting from (1, 1) and stopping if we reach cell (N, N). explore(x, y)

-------------

- Mark the current cell (x, y) as "visited."

- If no wall to north and unvisited, then explore(x, y+1).

- If no wall to east and unvisited, then explore(x+1, y).

- If no wall to south and unvisited, then explore(x, y-1).

- If no wall to west and unvisited, then explore(x-1, y).

Java

plaese include and imports/ main functions that you used to complie it, and show how you compiled it

typed out please! no pictures, please make it clear

comment each line

Explanation / Answer

def step(state, finish=false)
connected_sets = []
connected_set = [0]
(state.width-1).times do |c|
if state.same?(c, c+1) || (!finish && rand(2) > 0)
# cells are not joined by a passage, so we start a new connected set
connected_sets << connected_set
connected_set = [c+1]
else
state.merge(c, c+1)
connected_set << c+1
end
end
connected_sets << connected_set
verticals = []
next_state = state.next

unless finish
state.each_set do |id, set|
cells_to_connect = set.sort_by { rand }[0, 1 + rand(set.length-1)]
verticals.concat(cells_to_connect)
cells_to_connect.each { |cell| next_state.add(cell, id) }
end
end

row = []
connected_sets.each do |connected_set|
connected_set.each_with_index do |cell, index|
last = (index+1 == connected_set.length)
map = last ? 0 : E
map |= S if verticals.include?(cell)
row << map
end
end

[next_state.populate, row]
end
spinning = true
trap("INT") { spinning = false }

puts " " + "_" * (width * 2 - 1)
while spinning
state, row = step(state)
row_count += 1
puts row2str(row)
spinning = row_count+1 < height if height
end
state, row = step(state, true)
row_count += 1
puts row2str(row)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.