using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MazeBois
{
    class Program
    {
        public static MazeRepresentaion Maze { get; set; }
        static void Main(string[] args)
        {
            Maze = new MazeRepresentaion(@"
111111111
111111101
1111s1111
100000101
10101010g
101010101
111111111
111111111
");

            var result = TraverseThatBoi();
            PrintTraversalResult(result);
        }

        private static void PrintTraversalResult(Dictionary<Tuple<int, int>, int> result)
        {
            for (var i = 0; i < Maze.Rows; i++)
            {
                for (var j = 0; j < Maze.Cols; j++)
                {
                    Console.ForegroundColor = GetColor(i, j);
                    Console.Write($"     {Maze.AtPos(i, j)}     ");
                }
                Console.WriteLine();
                for (var j = 0; j < Maze.Cols; j++)
                {
                    Console.ForegroundColor = GetColor(i, j);
                    var tuple = new Tuple<int, int>(i, j);
                    if (result.ContainsKey(tuple))
                    {
                        Console.Write($"   ({result[tuple].ToString("D2")})    ");
                    }
                    else
                    {
                        Console.Write($"   (xx)    ");
                    }
                }
                Console.WriteLine("\n\n");
            }
            Console.ForegroundColor = ConsoleColor.White;
        }

        private static ConsoleColor GetColor(int i, int j)
        {
            var c = Maze.AtPos(i, j);
            if (c == 's') return ConsoleColor.Cyan;
            else if (c == 'g') return ConsoleColor.Cyan;
            else if (c == '1') return ConsoleColor.Green;
            else if (c == '0') return ConsoleColor.Red;
            return ConsoleColor.White;
        }

        private static Coord GetStart()
        {
            for (var i = 0; i < Maze.Rows; i++)
            {
                for (var j = 0; j < Maze.Cols; j++)
                {
                    if (Maze.AtPos(i, j) == 's')
                    {
                        return new Coord(i, j);
                    }
                }
            }
            return null;
        }

        private static Dictionary<Tuple<int, int>, int> TraverseThatBoi()
        {
            var marked = new Dictionary<Tuple<int, int>, int>();
            var moves = 0;
            var queue = new Queue<Coord>();
            queue.Enqueue(GetStart());
            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                if (marked.Any(e => e.Key.Item1 == current.X && e.Key.Item2 == current.Y)) continue;
                marked[new Tuple<int, int>(current.X, current.Y)] = moves++;

                // 🤷‍♀️🤷‍♀️🤷‍♀️🤷‍♀️🤷‍♀️
                var right = current.Down();
                var down = current.Right();
                var left = current.Up();
                var up = current.Left();
                if (Maze.Legal(right) && Maze.AtPos(right) != '0') queue.Enqueue(right);
                if (Maze.Legal(down) && Maze.AtPos(down) != '0') queue.Enqueue(down);
                if (Maze.Legal(left) && Maze.AtPos(left) != '0') queue.Enqueue(left);
                if (Maze.Legal(up) && Maze.AtPos(up) != '0') queue.Enqueue(up);
            }

            return marked;
        }
    }

    class Coord
    {
        public int X { get; set; }
        public int Y { get; set; }
        public Coord (int x, int y)
        {
            X = x;
            Y = y;
        }

        public Coord Up()
        {
            return new Coord(X, Y - 1);
        }
        public Coord Down()
        {
            return new Coord(X, Y + 1);
        }
        public Coord Left()
        {
            return new Coord(X - 1, Y);
        }
        public Coord Right()
        {
            return new Coord(X + 1, Y);
        }
    }

    class MazeRepresentaion
    {
        private string maze;
        public string Maze
        {
            get { return maze; }
            set
            {
                maze = value.Trim();
                RowsCache = maze.Split('\n').Select(e => e.Trim()).ToArray();
                Cols = RowsCache.First().Length;
            }
        }

        public int Rows => RowsCache.Length;
        public int Cols { get; private set; }

         private string[] RowsCache { get; set; }

        public MazeRepresentaion(string maze)
        {
            Maze = maze;
        }

        public char AtPos(int row, int col)
        {
            return RowsCache[row][col];
        }

        public char AtPos(Coord c)
        {
            return AtPos(c.X, c.Y);
        }

        public bool Legal(int row, int col)
        {
            return row >= 0 && row < Rows && col >= 0 && col < Cols;
        }

        public bool Legal(Coord c)
        {
            return Legal(c.X, c.Y);
        }
    }
}