人材獲得作戦 試験問題

解いた。
人材獲得作戦・4 試験問題ほか: 人生を書き換える者すらいた。
50分。C#。某貧乏国立中の中学生。


アルゴリズマーじゃないと思うんですけど、スラスラ解けたらカッコいいですよね。
情オリあるしなあ…。

言い訳
  • 距離の加算を++でしてた!アホい!(start地点からstart地点につくのに、int.MaxValue超えちゃう!
  • xとyを逆にしてた!(ありがち
  • iとjを(ry
  • 番兵おくかいちいちチェックするか迷ってた。初め番兵おいてたけど、途中でワケわかんなくなったので(まあその理由はxとyが逆だったからなんですけどね)、チェックする方にした。
その他
  • こういうのを綺麗にずばばばっと解けるようになりたい。
  • 逆にするとかケアレスミス大杉
  • xとyが混乱してきたんで、rowsとcolumnsにした。map[y,x]とか書きたくなかった。
  • うちの先輩の方らしいですね。
  • @俺 もっと勉強しなさい!!!!1111
using System.Collections;
using System.Collections.Generic;
using System.IO;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader reader = new StreamReader("map.txt");
            string[] rows = reader.ReadToEnd().Split('\n');
            int r = rows.Length, c = rows[r - 1].Length;
            char[,] map = new char[r, c];
            int[,] distance = new int[r, c];
            int[,][] prev = new int[r, c][];
            int sr = 0, sc = 0, gr = 0, gc = 0;

            for (int i = 0; i < r; i++)
                for (int j = 0; j < c; j++)
                {
                    map[i, j] = rows[i][j];
                    switch (map[i, j])
                    {
                        case 'S':
                            sr = i;
                            sc = j;
                            break;
                        case 'G':
                            gr = i;
                            gc = j;
                            break;
                    }
                    distance[i, j] = int.MaxValue;
                }

            distance[sr, sc] = 0;
            Queue<int[]> queue = new Queue<int[]>();
            queue.Enqueue(new int[] { sr, sc });
            for (int i = sr; i != gr; )
                for (int j = sc; j != gc; )
                {
                    if (map[i, j] == 'G')
                        break;
                    int[] t = queue.Dequeue();
                    i = t[0];
                    j = t[1];
                    if (j + 1 < c && map[i, j + 1] != '*')
                        if (distance[i, j + 1] > distance[i, j] + 1)
                        {
                            distance[i, j + 1] = distance[i, j] + 1;
                            prev[i, j + 1] = new int[] { i, j };
                            queue.Enqueue(new int[] { i, j + 1 });
                        }
                    if (j - 1 >= 0 && map[i, j - 1] != '*')
                        if (distance[i, j - 1] > distance[i, j - 1] + 1)
                        {
                            distance[i, j - 1] = distance[i, j] + 1;
                            prev[i, j - 1] = new int[] { i, j };
                            queue.Enqueue(new int[] { i, j - 1 });
                        }
                    if (i + 1 < r && map[i + 1, j] != '*')
                        if (distance[i + 1, j] > distance[i, j] + 1)
                        {
                            distance[i + 1, j] = distance[i, j] + 1;
                            prev[i + 1, j] = new int[] { i, j };
                            queue.Enqueue(new int[] { i + 1, j });
                        }
                    if (i - 1 >= 0 && map[i - 1, j] != '*')
                        if (distance[i - 1, j] > distance[i, j] + 1)
                        {
                            distance[i - 1, j] = distance[i, j] + 1;
                            prev[i - 1, j] = new int[] { i, j };
                            queue.Enqueue(new int[] { i - 1, j });
                        }
                }

            for (int i = gr, j = gc; i != sr || j != sc; )
            {
                map[i, j] = '$';
                int[] t = prev[i, j];
                i = t[0];
                j = t[1];
            }
            
            map[sr, sc] = 'S';
            map[gr, gc] = 'G';

            StreamWriter writer = new StreamWriter("result.txt");
            for (int i = 0; i < r; i++)
            {
                for (int j = 0; j < c; j++)
                    writer.Write(map[i, j]);
                writer.WriteLine();
            }

            reader.Close();
            writer.Close();
        }
    }
}