“人生を書き換える者すらいた。”の迷路問題を解いてみた

今更感はあるのだけれど，気分転換に下記のブログで紹介されてた問題を解いてみた．

人生を書き換える者すらいた。 人材獲得作戦・４ 試験問題ほか

かかった時間はたぶん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();
        }