Skip to content

Instantly share code, notes, and snippets.

@kyanny kyanny/bfs.rb
Created Jan 17, 2019

Embed
What would you like to do?
require 'thread'
V = Struct.new(:x, :y, :visited, :goal)
m = []
$w = 10
$h = 10
$h.times do |h|
l = []
$w.times do |w|
l << V.new(w, h)
end
m << l
end
m[-1][-1].goal = true
#m << [V.new(0, 0), V.new(0, 1), V.new(0, 2)]
#m << [V.new(1, 0), V.new(1, 1), V.new(1, 2)]
#m << [V.new(2, 0), V.new(2, 1), V.new(2, 2, nil, true)]
#visited = [['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']]
visited = []
$h.times do
l = []
$w.times do |w|
l << '-'
end
visited << l
end
p visited
def fmt(visited)
_visited = visited.dup
loop do
break if _visited.empty?
puts _visited.shift.join
end
puts ''
end
def bfs(v, m, visited)
finished = false
q = Queue.new
v.visited = true
visited[v.x][v.y] = 'x'
q.enq v
loop do
break if q.empty?
v = q.deq
visited[v.x][v.y] = 'x'
fmt(visited)
if v.goal == true
finished = v
visited[v.x][v.y] = '$'
break
end
if v.x > 0
v_left = m[v.x-1][v.y]
unless v_left.visited == true
v_left.visited = true
q.enq v_left
end
end
if v.y > 0
v_top = m[v.x][v.y-1]
unless v_top.visited == true
v_top.visited = true
q.enq v_top
end
end
if v.x < $w-1
v_right = m[v.x+1][v.y]
unless v_right.visited == true
v_right.visited = true
q.enq v_right
end
end
if v.y < $h-1
v_bottom = m[v.x][v.y+1]
unless v_bottom.visited == true
v_bottom.visited = true
q.enq v_bottom
end
end
end
if finished
p finished
else
puts 'not found'
end
end
bfs m[0][0], m, visited
fmt(visited)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.