2010年1月14日木曜日

話題になってるアレ

 アレですが、問題をよく読んでいなくて、入力テキストが長方形と保証されていないものとして、とっかかって25分ほど費やしてやめた。長方形と保証されていなければ、とても3時間で解ける代物では無さそうだからだ。グラフ構造に落とし込んでも、元のテキストに復元する事まで考えると、結構難しい。
 結局、ポイントは、二次元配列で扱える事なのだろう。後は、スタート位置から進行可能な上下左右位置に1歩づつ訪問済みのマークを付けて、訪問済みの位置は壁として扱い、進行可能な限り上下左右を再帰していけば解けるのだろう。
ただし、1歩づつ再帰しないといけないので、ここも難しい。一歩づつでなければ最短経路を見つけるのは難しい。結局グラフ構造に落とし込まないといけない。
 という訳で、あんたすげーよ。

0 件のコメント: