不格好エンジニア (引っ越しました)

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

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

TopCoder SRM453.5 Div2 Level2を解いてみました。

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

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

[問題要約]
友人の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