今更感はあるのだけれど,気分転換に下記のブログで紹介されてた問題を解いてみた.
人生を書き換える者すらいた。 人材獲得作戦・4 試験問題ほか
かかった時間はたぶん60分ぐらい.アルゴリズム的にはAアルゴリズムを使えば良いらしいけど,正直なところ,よく知らないので,適当に自分で考えてみた.
基本的な考え方としては,距離1で行ける場所,距離2で行ける場所,距離nで行ける場所を順にピックアップしていき,距離nでゴールまで行けるようになったら,そこから逆に最短となる経路を探す,といった感じ.
コメント欄を見てると30分とかで解いてる人も居るっぽいので,私はまだまだだなぁという感じですね.せっかくなので,ソースコードを公開してみます.あんまり綺麗なコードじゃないので,参考にはしないほうがよいと思うけど.
static void Main(string[] args) { / ファイルを読み込みrawdata上に展開 */string line = ""; ArrayList rawdata = new ArrayList(); StreamReader sr = new StreamReader(@"data.txt", Encoding.GetEncoding("Shift_JIS")); while ((line = sr.ReadLine()) != null) { rawdata.Add(line); } /* * rawdata上のデータをint型二次元配列dataに展開 * 壁:-1 * スタート位置:1 * ゴール位置:-10 * 道:0 */ int[,] data; string tmp = rawdata[0] as string; int width = tmp.Length; int height = rawdata.Count; data = new int[width, height]; for (int i = 0; i < height; i++) { tmp = rawdata[i] as string; for (int j = 0; j < width; j++) { if (tmp[j] == '*') { data[j, i] = -1; } else if (tmp[j] == 'S') { data[j, i] = 1; } else if (tmp[j] == 'G') { data[j, i] = -10; } else { data[j, i] = 0; } } } /* * data配列をスタート位置から走査して, * スタート位置からの距離を格納する. * ゴール(-10)を見つけたらループを抜ける. */ int cur = 1; bool loopflag = true; while (loopflag) { for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { if (data[j, i] == cur) { if (data[j, i - 1] == -10 || data[j - 1, i] == -10 || data[j, i + 1] == -10 || data[j + 1, i] == -10) { loopflag = false; break; } if (data[j, i - 1] == 0) { data[j, i - 1] = cur + 1; } if (data[j - 1, i] == 0) { data[j - 1, i] = cur + 1; } if (data[j, i + 1] == 0) { data[j, i + 1] = cur + 1; } if (data[j + 1, i] == 0) { data[j + 1, i] = cur + 1; } } } if (!loopflag) { break; } } cur++; } /* * data配列をゴール位置から走査して, * スタート位置に向けて-2を格納していく. * スタート位置を見つけたらループを抜ける. */ loopflag = true; while (loopflag) { cur--; if (cur == 1) { break; } for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { if (data[j, i] == -10 || data[j, i] == -2) { if (data[j, i - 1] == cur) { data[j, i - 1] = -2; }else if (data[j - 1, i] == cur) { data[j - 1, i] = -2; } else if (data[j, i + 1] == cur) { data[j, i + 1] = -2; } else if (data[j + 1, i] == cur) { data[j + 1, i] = -2; } } } } } /* * 画面に表示を行う. */ for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { if (data[j, i] == -1) { Console.Write('*'); } else if (data[j, i] == 1) { Console.Write('S'); } else if (data[j, i] == -10) { Console.Write('G'); } else if (data[j, i] >= 0) { Console.Write(' '); } else if (data[j, i] == -2) { Console.Write('$'); } else { Console.Write(data[j, i]); } } Console.Write('\n'); } Console.Write('\n'); Console.Read(); }</pre>