今更感はあるのだけれど，気分転換に下記のブログで紹介されてた問題を解いてみた．
人生を書き換える者すらいた。 人材獲得作戦・４ 試験問題ほか
かかった時間はたぶん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>
