using System;
using System.Collections.Generic;
using System.Text;

namespace Maze
{
    class Maze
    {
        public class Path
        {
            public Dictionary<int, bool> rooms = new Dictionary<int, bool>();
            public Dictionary<Path, bool> neighbors = new Dictionary<Path, bool>();
            public Dictionary<int, bool> deletedColumnWalls = new Dictionary<int, bool>();
            public Dictionary<int, bool> deletedRowWalls = new Dictionary<int, bool>();

            public Path(int id)
            {
                rooms.Add(id, true);
            }

            public override String ToString()
            {
                return rooms.ToString();
            }
        }

        int row;
        int column;
        Random rand = new Random();
        List<Path> paths = new List<Path>();

        static void Main(string[] args)
        {
            Maze m = new Maze();
            m.row = 10;
            m.column = 10;
            m.run();
            m.printResult();
        }

        char EMPTY = '　';
        private char[] GRID = {
            '　','┃','━','┏',
            '━','┓','━','┳',
            '┃','┃','┗','┣',
            '┛','┫','┻','╋'
        };
        
        private void printResult() {
            char[][] grid = new char[row * 2 + 2][];//[column * 2 + 2];
            for (int i = 0; i < grid.Length; i++)
            {
                grid[i] = new char[column * 2 + 2];
                for(int z = 0; z < grid[i].Length; z++)
                    grid[i][z] = EMPTY;
            }
            Path path = paths[0];
            for(int rowIndex = 0; rowIndex <= row; rowIndex++) {
                for(int columnIndex = 0; columnIndex <= column; columnIndex++) {
                    int id = columnIndex + rowIndex * column;
                    bool leftWall = rowIndex != row && (columnIndex == 0 || columnIndex == column || !path.deletedColumnWalls.ContainsKey(id - 1));
                    bool topWall = columnIndex != column && (rowIndex == 0 || rowIndex == row || !path.deletedRowWalls.ContainsKey(id - column));
                    bool leftTopWall = columnIndex != 0 && (rowIndex == 0 || rowIndex == row || !path.deletedRowWalls.ContainsKey(id - column - 1));
                    bool topLeftWall = rowIndex != 0 && (columnIndex == 0 || columnIndex == column || !path.deletedColumnWalls.ContainsKey(id - column - 1));

                    grid[rowIndex * 2 + 1][columnIndex * 2 + 1] = EMPTY;
                    grid[rowIndex * 2 + 1][columnIndex * 2] = leftWall ? '┃' : EMPTY;
                    grid[rowIndex * 2][columnIndex * 2 + 1] = topWall ? '━' : EMPTY;
                    
                    int index = 0;
                    index |= leftWall ? 1 : 0;
                    index |= topWall ? 2 : 0;
                    index |= leftTopWall ? 4 : 0;
                    index |= topLeftWall ? 8 : 0;
                    grid[rowIndex * 2][columnIndex * 2] = GRID[index];
                }
            }
            grid[1][0] = EMPTY;
            grid[row * 2 - 1][column * 2] = EMPTY;
            for (int rowIndex = 0; rowIndex < grid.Length - 1; rowIndex++)
            {
                for (int columnIndex = 0; columnIndex < grid[row].Length - 1; columnIndex++)
                    Console.Write(grid[rowIndex][columnIndex]);
                Console.WriteLine();
            }
        }


            
        private void run()
        {
            for (int x = 0; x < row; x++)
            {
                for (int y = 0; y < column; y++)
                {
                    int id = x * column + y;
                    Path path = new Path(id);

                    if (y > 0)
                    {
                        Path left = paths[paths.Count - 1];
                        left.neighbors.Add(path, true);
                        path.neighbors.Add(left, true);
                    }
                    if (x > 0)
                    {
                        Path top = paths[paths.Count - column];
                        top.neighbors.Add(path, true);
                        path.neighbors.Add(top, true);
                    }
                    paths.Add(path);
                }
            }
            while (paths.Count > 1)
                mergePaths();
        }

        private void mergePaths() {
            Path first = paths[rand.Next(paths.Count)];

            List<int> options = new List<int>();
            for(int i = 0; i < paths.Count; i++) {
                Path tmp = paths[i];
                if(first != tmp) {
                    if(first.neighbors.ContainsKey(tmp))
                        options.Add(i);
                }
            }
            
            int secondIndex = options[rand.Next(options.Count)];
            Path second = paths[secondIndex];
            
            List<List<int>> connectWalls = getConnectWall(first, second);
            int wallIndex = rand.Next(connectWalls[0].Count + connectWalls[1].Count);
            if(wallIndex < connectWalls[0].Count)
                first.deletedRowWalls.Add(connectWalls[0][wallIndex], true);
            else
                first.deletedColumnWalls.Add(connectWalls[1][wallIndex - connectWalls[0].Count], true);
            
            first.neighbors.Remove(second);
            second.neighbors.Remove(first);
            foreach(Path secondNeighbor in second.neighbors.Keys) {
                secondNeighbor.neighbors.Remove(second);
                if(!secondNeighbor.neighbors.ContainsKey(first))
                    secondNeighbor.neighbors.Add(first, true);
                if(!first.neighbors.ContainsKey(secondNeighbor))
                    first.neighbors.Add(secondNeighbor, true);
            }
            foreach(int room in second.rooms.Keys)
                first.rooms.Add(room, true);
            
            foreach(int wall in second.deletedRowWalls.Keys)
                first.deletedRowWalls.Add(wall, true);
            foreach (int wall in second.deletedColumnWalls.Keys)
                first.deletedColumnWalls.Add(wall, true);
            
            paths.RemoveAt(secondIndex);
        }

        private List<List<int>> getConnectWall(Path first, Path second) {
            List<List<int>> result = new List<List<int>>();
            List<int> rowWalls = new List<int>();
            List<int> columnWalls = new List<int>();
            result.Add(rowWalls);
            result.Add(columnWalls);

            bool firstLess = first.rooms.Count <= second.rooms.Count;
            Dictionary<int, bool> rooms = firstLess ? first.rooms : second.rooms;
            Dictionary<int, bool> secondRooms = firstLess ? second.rooms : first.rooms;
            foreach(int room in rooms.Keys) {
                if(secondRooms.ContainsKey(room - column))
                    rowWalls.Add(room - column);
                if (secondRooms.ContainsKey(room + column))
                    rowWalls.Add(room);

                int columnIndex = room % column;
                if (columnIndex > 0 && secondRooms.ContainsKey(room - 1))
                    columnWalls.Add(room - 1);
                if (columnIndex < column - 1 && secondRooms.ContainsKey(room + 1))
                    columnWalls.Add(room);
            }
            return result;
        }

    }
}