bfs.rb

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)