Ruby練習6 (Red and Black)
前回に引き続きACM/ICPC国内予選突破の手引きより問題を選んでみる。今回は難易度を一つ挙げて☆2つ。選んだのはRed and Blackという問題。
def walk(tiles, x, y, count) if x < 0 || y < 0 || x >= tiles[0].size || y >= tiles.size return count end if tiles[y][x] == "#" return count end tiles[y][x] = "#" # 一度訪れた場所は赤にする count += 1 count = walk(tiles, x + 1, y, count) count = walk(tiles, x, y + 1, count) count = walk(tiles, x - 1, y, count) count = walk(tiles, x, y - 1, count) return count end while true w, h = ARGF.gets.chomp.split(/ /).map { |v| v.to_i } if w == 0 && h == 0 break end # 部屋の初期化 tiles = [] h.times { |i| tiles << ARGF.gets.chomp.split("") } # スタート地点を検索 start_x = 0 start_y = 0 tiles.each_with_index { |line, y| break unless line.each_with_index { |tile, x| if tile == "@" start_x = x start_y = y break end } } # 探査 puts walk(tiles, start_x, start_y, 0) end
感想
walk() の4番目の引数 count を入出力を兼ねた変数として使いたかったけど、なかなか思うようにいかず、入力のみとした。Ruby ではメソッドの引数は参照渡しということなので、walk() 内で count の値を変更すれば呼び出し元の変数も副作用を受けると思ったのだが。tiles は期待通りの動きをしてるんだけど...。リファレンスによると、
仮引数は、ローカル変数であり、仮引数に代入を行うと他のオブジェクトを指すようになるだけで、元の実引数のオブジェクトには何の影響もありません。
プログラミング言語 Ruby リファレンスマニュアル
ということらしい。ここでやりたかったのは代入ではなく count += 1 (インクリメント) なのだが、これでも代入になるようだ。まあ、これは count = count + 1 なので代入だし、当然か。そこで、代入ではなく count が指しているオブジェクトの中身を変更できる(破壊的)方法はないかと探していたところ、
また、同じ数を表わすFixnumのインスタンスは常に同じものになりますので、インスタンス変数を定義した場合には、それも同じものを示すことになります。
プログラミング言語 Ruby リファレンスマニュアル
ということらしい。Fixnum は値によって指すオブジェクトが決まっているのか?実際に試してみると、
num1 = 1 p num1.object_id # => 3 num2 = 1 p num2.object_id # => 3
となり、num1 と num2 は同じオブジェクトを指している。もし、代入を使わずに値を変更できる方法があったとしても、Fixnum の場合は、指し示すオブジェクトは変わってしまうのかな。そういうわけで walk() の count は入出力の引数とせずに、入力値としての引数にした。count を Fixnum ではなく、Array などにすればできなくもないが、それはそれで不自然な気がしてやめた。グローバル変数でもよかったけど、グローバル変数は使うなっていうからね。これくらいの規模なら問題はないと思うけど。
ちなみに、他のクラスで同じ値を持たせた場にオブジェクトIDはどうなるかというと (ここでは String クラスで試してみた)、
str1 = "hoge" p str1.object_id # => 84070 str2 = "hoge" p str2.object_id # => 84050
同じ値でも指しているオブジェクトは異なっている。