蟻本の序盤で出てくる深さ優先探索を練習すべくこの問題をやっていた。
atcoder.jp
最終的にこんな感じに落ち着いて、まぁ解説通りだろっていう感じです。
ENV[Z='RUBY_THREAD_VM_STACK_SIZE']||exec({Z=>'100000000'},'ruby',$0)
(N, M) = gets.chomp.split.map(&:to_i)
@a = readlines.map{|l| l.chomp.chars}
def search(x, y)
return false unless x >= 0 && x < ::N && y >= 0 && y < ::M
return false if @a[x][y] == '#'
return true if @a[x][y] == 'g'
@a[x][y] = '#'
return true if search(x+1, y)
return true if search(x, y+1)
return true if search(x-1, y)
return true if search(x, y-1)
false
end
result = false
(0...N).each do |x|
(0...M).each do |y|
if @a[x][y] == 's'
result = search(x, y)
end
end
end
puts result ? 'Yes' : 'No'
RUBY_THREAD_VM_STACK_SIZE を変更しないといけない
ただ、ここに至るにはいくつかの問題があって結構苦労した。
コード自体はわりとすぐ書けたんだけど、どうにもRuntimeErrorがでている。
しかも提出結果がREになるだけで、具体的にどんなエラーが出ているかわからない。
どうしようもないので、Rubyの正解コードを見ていると共通点があった。
RUBY_THREAD_VM_STACK_SIZE 環境変数を指定している。これは以下の通り。
RUBY_THREAD_VM_STACK_SIZE: スレッドを作る時に作成する VM スタックサイズ（デフォルト: 128KB (32bit CPU) or 256KB (64bit CPU)）
https://magazine.rubyist.net/articles/0041/0041-200Special-note.html
どうやら再帰呼びだしのスタックが溢れちゃってRuntimeErrorがでるので、そのサイズを大きくしてエラーがでないようにしよう、ということ。
しかしRUBY_THREAD_VM_STACK_SIZE はプログラム実行中には変更できない仕様なので、
exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'}, 'ruby', $0)
としてスクリプトを再実行する必要がある。
らしい。
これは知らなかったらわからない案件ですね。
再帰関数内で変数使わないほうがいい
RUBY_THREAD_VM_STACK_SIZEの対処がわかって、これでイケるだろうと思ったけど今度はメモリ不足。
その時のコードはこんな感じ
def reach_goal?(x, y)
dx = [ 0, 1, -1, 0]
dy = [-1, 0, 0, 1]
(0..3).each do |i|
nx = x + dx[i]
ny = y + dy[i]
next unless nx >= 0 && nx < ::N && ny >= 0 && ny < ::M
return true if @a[nx][ny] == 'g'
next if @a[nx][ny] == '#'
next if @reached[nx][ny]
@reached[nx][ny] = true
return true if reach_goal?(nx, ny)
end
return false
end
メソッドのコールスタックに配列とかループとかそのへんのデータを乗せる必要になるから、たぶんそういうことだろう。 それで、関数内の変数とかループとかをなくして、コールスタックに積むデータをなるべく減らすようにコードを改善したらクリアできた。めでたしめでたし。
わからない時は答えをみればよい
わからない時は正解のコードを見ればよい。アルゴリズム自体には問題はなかったけど、実装方法に問題があった、って感じだ。
わからない時は答えみればいいし、それで理解できたらいいのだ。
幸いAtCoderには解説のPDFとYouTube動画があるし、正解のコードもいろいろ見れるので、学ぶには良い環境だ。
こぼれ話は、原因がわからないときにRustでやってみようと思って試したけど、最初の迷路データをSTDINから取得する部分で詰んだ。Rustむずい。っていう話。
