読者です 読者をやめる 読者になる 読者になる

kur.jp

バイオリンと自転車をこよなく愛するkurのチラシの裏。たまには技術的なことを書いたりするかも知れません。

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

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

人生を書き換える者すらいた。 人材獲得作戦・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>