最終更新: 2011-02-13T06:07+0900
3問あるうちの 2問目を抜粋する。
問2. 7×7の二次元配列aがあるとする。たとえば、以下のようなものである。
int a[7,7] ={ {1,1,1,1,1,1,1}, {1,0,0,0,0,0,1}, {1,0,1,1,1,0,1}, {1,0,0,0,1,1,1}, {1,0,0,1,0,0,1}, {1,0,0,0,1,0,1}, {1,1,1,1,1,1,1} };いま、aを迷路と見立てる。a[x,y]が0の箇所は歩けて、1の箇所は歩けない。迷路の外周は1であることが保証されているとする。
a[x,y]をスタート地点として、この迷路を歩いていくときの、歩ける箇所の数を求める関数W(a,x,y)を書け。(上の例では、W(a,1,1)=15)
ただし、再帰を使ったプログラム、再帰を使わないプログラムを用意すること。また、配列aの内容は破壊しても構わない。
トイレに入ってるときに前後の脈絡もなく答えが天から降ってきたので再帰版のRubyスクリプトを載っけてみる。再帰版は 1行で書けるらしいのだけど……。
# # 再帰版 # def w(a, x, y) if(x<0 || y<0 || a.length<=x || a[x].length<=y || a[x][y]==1) return 0; else a[x][y] = 1; return 1 + w(a, x-1, y) + w(a, x, y-1) + w(a, x+1, y) + w(a, x, y+1); end end a = [ [1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1], [1, 0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 0, 0, 1], [1, 0, 0, 0, 1, 0, 1], [1, 1, 1, 1, 1, 1, 1] ]; puts w(a, 1, 1); #=> 15
他の問題は解らない(というか考えてない(ってのは言い訳か))。問3なんて問題が理解できません。
芸がなくて恥ずかしいけど、スタックをキュー仮想スタックにしただけの非再帰版もアップ。
# # 非再帰版 # def w(a, x, y) ret = 0; q = x, y; while(! q.empty?) x, y = q.pop; if(x<0 || y<0 || a.length<=x || a[x].length<=y || a[x][y]==1) next; else ret += 1; a[x][y] = 1; q.push([x-1, y], [x, y-1], [x+1, y], [x, y+1]); end end return ret; end a = [ [1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1], [1, 0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 0, 0, 1], [1, 0, 0, 0, 1, 0, 1], [1, 1, 1, 1, 1, 1, 1] ]; puts w(a, 1, 1); #=> 15
最終更新: 2011-02-13T06:07+0900
引用文の表現力が上がってるのだけど、もうひとつ、引用の中で整形済みテキスト(pre)を使いたい。
すぐ上のセクション(↑)で、改行を維持するために引用の中のコード部分だけを<pre>で囲ってるのだけど、そのソースはちょっと汚い。(上から二行目と下から二行目で)直接HTMLを埋め込んでるから後々 tDiaryをXHTML化したりするのが難しくなる。HTML化はWikiパーサに全て任せたい。tdiary/hikidoc.rbを拡張して引用文中の<pre>が可能にならないものか。
""7×7の二次元配列aがあるとする。たとえば、以下のようなものである。
"" int a[7,7] ={
"" {1,1,1,1,1,1,1},
"" {1,0,0,0,0,0,1},
"" {1,0,1,1,1,0,1},
"" {1,0,0,0,1,1,1},
"" {1,0,0,1,0,0,1},
"" {1,0,0,0,1,0,1},
"" {1,1,1,1,1,1,1}
"" };
""いま、aを迷路と見立てる。a[x,y]が0の箇所は歩けて、1の箇所は歩けな