RubyでTopCoderの問題を解いてみる(幅優先探索)

※旧ブログからの転載記事です。

幅優先探索をはじめて実装しました。長くて見通しがよくない気がする。。。リファクタが必要。

[問題要約]
友人のjimに迷路を解かせたいと思っています。Jimの動き方は、move_row, move_colで指定されています。
障害物は'X'で表し、通行できる場所は'.'で表します。
出口をなるべくスタート地点から遠いところに置いて、出口に到達するまでのステップ数を返せ。
到達できない時は-1を返せ。



# coding: utf-8

# SRM453.5 Div2 Level2

# 幅優先探索

# 迷路を解いたり、最短経路のステップ数を知ることもできるアルゴリズム

# step1:ある出発点から1つ進んだ経路をすべて求める

# step2:これらの経路から1つ進んだ経路をすべて求める

# setp3:上記の作業をゴールに至るまで繰り返す
require 'pp'

class MazeMaker
  def longest_path(maze, start_row, start_col, move_row, move_col)

    max = 0 # 最大ステップ数

    width = maze[0].size # 幅

    height = maze.size # 高さ
    board = Array.new(height).map{Array.new(width, -1)} # 盤面(すべての経路を初期化)
    # スタート地点を選ぶ

    #boardのスタート地点には0と書いておく、次の地点には1, その次の地点には2,...と順次増やす

    board[start_row][start_col] = 0
   # queueを用意する

   queue_x = Array.new

   queue_y = Array.new
   queue_x.push(start_col)

   queue_y.push(start_row)
   while queue_x.size > 0 do

     # 1つの地点を取り出す

     x = queue_x.pop

     y = queue_y.pop
     # 選んだ地点から1つずつ進んだ経路を調べる

     for i in 0..(move_row.size-1) do

       next_x = x + move_col[i]

       next_y = y + move_row[i]
       # 以下の条件なら探索を続ける(queueに格納する)

       # 盤面上にある場所

       # まだ行ったことがない

       # 通行可能な場所

       #pp "next_x = #{next_x}, next_y = #{next_y}, x=#{x}, y=#{y}" # debug
       next unless (0 <= next_x && next_x < width && 0 <= next_y && next_y < height)

       next unless board[next_y][next_x] == -1

       next unless  maze[next_y][next_x] == '.'
       board[next_y][next_x] = board[y][x] + 1 #移動先は、現在の地点から1加算した値を書いておく
       queue_x.push(next_x)

       queue_y.push(next_y)
     end
   end # end while
   # 一通り、盤面を眺めて、まだ行ってない地点があるとしたら、それは到達できない地点だと言う事

   for i in 0..(height-1) do

     for j in 0 ..(width-1) do

       if maze[i][j] == '.' && board[i][j] == -1 #到達していない点があった

         return -1

       else

         max = [max, board[i][j]].max

       end

     end

   end

   return max
  end

end


#

#== example 0

#

maze = [

  ['.', '.', '.'],

  ['.', '.', '.'],

  ['.', '.', '.']

]

start_row = 0

start_col = 1

move_row = [0,0,-1,1]

move_col = [-1,1,0,0]
ret = MazeMaker.new.longest_path(maze, start_row, start_col, move_row, move_col)

pp "correct!" if ret == 3
#

#== example 2

#

#

maze = [

  ['X','.','X'],

  ['.','.','.'],

  ['X','X','X'],

  ['X','.','X'],

]
start_row = 0

start_col = 1

move_row = [1,0,-1,0]

move_col = [0,1,0,-1]ret = MazeMaker.new.longest_path(maze, start_row, start_col, move_row, move_col)

pp "correct!" if ret == -1

不格好エンジニア

wordpress.comから引っ越しました。

RubyでTopCoderの問題を解いてみる(幅優先探索)