Day 18 | C# Online Compiler

Day 18 by Pieter Peeters

using System;
using System.Linq;
using System.Collections.Generic;
public class Program
{
	
	public static void Main()
	{	
		Map map = new Map(Input.INPUT2);
		List<char> keys = new List<char>();
		
		int pathLength = 0;
		map.FindKeyOrder(out pathLength, keys);
				
		Console.WriteLine("Keys: " + string.Join(",", keys));
		Console.WriteLine("Distance: " + pathLength);
		
	}
	
	public enum Direction {
		None = -1,
		East = 0,
		North = 1,
		West = 2,
		South = 3,
	}
	
	public struct Vec2 : IEquatable<Vec2> {
		public int x, y;	
		
		public Vec2(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		public static Vec2 operator+(Vec2 a, Vec2 b) {
			return new Vec2() { x = a.x + b.x, y = a.y + b.y };
		}	
		
		public static Vec2 operator+(Vec2 v, Direction dir) {
			switch (dir) {
				case Direction.North:
					v.y -= 1;
					break;
				case Direction.South:
					v.y += 1;
					break;
				case Direction.West:
					v.x -= 1;
					break;
				case Direction.East:
					v.x += 1;
					break;
			}
			return v;
		}
		
		public Direction GetDirection(Vec2 other) {
			if (other.x == x && other.y == y)
				return Direction.None;
			
			if (Math.Abs(other.x - x) > Math.Abs(other.y - y)) {
				if (other.x > x)
					return Direction.East;
				return Direction.West;
			}
			else {
				if (other.y > y)
					return Direction.South;
				return Direction.North;
			}
			
		}
		
		public int GetManhattan(Vec2 other) {
			return Math.Abs(x - other.x) + Math.Abs(y - other.y);	
		}
		
		public static bool operator==(Vec2 a, Vec2 b) {
			return a.x == b.x && a.y == b.y;	
		}
		
		public static bool operator!=(Vec2 a, Vec2 b) {
			return a.x != b.x || a.y != b.y;	
		}
		
		public override string ToString() {
			return "(" + x + ", " + y + ")";	
		}
		
        public override int GetHashCode()
        {
            return x.GetHashCode() ^ (y.GetHashCode() << 2);
        }
		
		public override bool Equals(object o) {
			Vec2 other = (Vec2)o;
			return other.x == x && other.y == y;
		}
		public bool Equals(Vec2 other) {
			return other.x == x && other.y == y;
		}
	}
	
	public class Map {
		
		public const char UNKNOWN = (char)0;
		public const char EMPTY = '.';
		public const char WALL = '#';
		
		private List<Vec2> robotPositions = new List<Vec2>();
		private char[] tiles;
		private Vec2 offset;
		private Vec2 size;
		private Dictionary<char, Vec2> keys = new Dictionary<char, Vec2>();
		private Dictionary<char, Vec2> doors = new Dictionary<char, Vec2>();
		
		public Map Copy() {
			Map result = new Map();
			
			result.robotPositions.AddRange(robotPositions);
			result.tiles = new char[tiles.Length];
			Array.Copy(tiles, result.tiles, tiles.Length);
			
			result.offset = offset;
			result.size = size;
			
			result.keys = new Dictionary<char, Vec2>(keys);
			result.doors = new Dictionary<char, Vec2>(doors);
			
			return result;			
		}
		
		private Map() {
		}
		
		public Map(string input)
		{
			Vec2 pos = new Vec2(0, 0);
			for (int i = 0; i < input.Length; ++i) {
				char c = input[i];
				if (c == '\n') {
					pos.y ++;
					pos.x = 0;
					continue;
				}
				if (c == '@') {
					robotPositions.Add(pos);	
					SetTile(pos, '.');
				}
				else {
					SetTile(pos, c);	
				}
				
				pos.x++;
			}
		}
		
		public void SetRobotPosition(int index, Vec2 position) {
			robotPositions[index] = position;	
			AddPosition(position);
		}
		
		public void SetTile(Vec2 position, char tile) {
			AddPosition(position);
			
			if (IsDoor(tile)) {
				doors[tile] = position;	
			}
			
			if (IsKey(tile)) {
				keys[tile] = position;	
			}
			
			tiles[position.x - offset.x + (position.y - offset.y) * size.x] = tile;
		}
		
		public char GetTile(Vec2 position) {
			position.x -= offset.x;
			position.y -= offset.y;
			
			if (position.x < 0 || position.y < 0)
				return UNKNOWN;
			
			if (position.x >= size.x || position.y >= size.y)
				return UNKNOWN;
			
			return tiles[position.x + position.y * size.x];
		}
		
		public Vec2 GetPosition(char c) {
			if (keys.ContainsKey(c))
				return keys[c];
			
			if (doors.ContainsKey(c))
				return doors[c];
			
			throw new Exception(c + " not found in map");
		}
		
		private void AddPosition(Vec2 newPosition) {
			int newOffsetX = Math.Min(newPosition.x, offset.x);
			int newOffsetY = Math.Min(newPosition.y, offset.y);
			
			int newWidth = Math.Max(newPosition.x - newOffsetX + 1, size.x - newOffsetX + offset.x);
			int newHeight = Math.Max(newPosition.y - newOffsetY + 1, size.y - newOffsetY + offset.y);
			
			if (size.x >= newWidth && size.y >= newHeight && newOffsetX >= offset.x && newOffsetY >= offset.y)
				return;
			
			char[] newTiles = new char[newWidth * newHeight];
			if (tiles != null) {
				for (int y = 0; y < size.y; ++y) {
					for (int x = 0; x < size.x; ++x) {	
						newTiles[x + offset.x - newOffsetX + (y + offset.y - newOffsetY) * newWidth] = tiles[x + y * size.x];
					}
				}
			}	
			offset.x = newOffsetX;
			offset.y = newOffsetY;
			tiles = newTiles;
			size.x = newWidth;
			size.y = newHeight;
		}
		
		public void Display() 
		{
			for (int y = 0; y < size.y; ++y) {
				for (int x = 0; x < size.x; ++x)
				{
					bool drawRobot = false;
					foreach (Vec2 robotPosition in robotPositions)
					{
						if ((robotPosition.x - offset.x) == x && (robotPosition.y - offset.y) == y) {
							Console.Write("@");
							drawRobot = true;
							break;
						}
					}
					
					if (drawRobot)
						continue;
					
					char c = tiles[x + y * size.x];
					
					if (c == 0)
						c = ' ';
					Console.Write(c);
				}
				Console.WriteLine();
			}
		}
		
		public void TakeKey(char c) {
			if (!IsKey(c))
				throw new Exception(c + " is not a key");
			
			SetTile(keys[c], '.');
			keys.Remove(c);
			
			char door = char.ToUpper(c);
			if (Exists(door)) {
				OpenDoor(door);	
			}
		}
		
		public bool Exists(char c) {
			return keys.ContainsKey(c) || doors.ContainsKey(c);	
		}
		
		public void OpenDoor(char c) {
			if (!IsDoor(c))
				throw new Exception(c + " is not a key");
			
			SetTile(doors[c], '.');
			doors.Remove(c);
		}
		
		private static Dictionary<string, (int, List<char>)> keysToPath
			= new Dictionary<string, (int, List<char>)>();

		private static int level = 0;
		
		public void FindKeyOrder(out int bestPathLength, List<char> path) {

			if (keys.Count == 0)
			{
				bestPathLength = 0;
				return;
			}

			level++;
			
			var reachable = FindReachable(robotPositions, IsKey);
						
			bestPathLength = int.MaxValue;
			
			foreach (var kvp in reachable)
			{
				if (level < 2)
				{
					Console.WriteLine("Starting with key " + kvp.Key);
				}
				Vec2 position = GetPosition(kvp.Key);
				int toKeyPath = GetPathLength(robotPositions[kvp.Value], position);

				HashSet<char> keysLeft = new HashSet<char>(keys.Keys);
				keysLeft.Remove(kvp.Key);

				Vec2 tempRP = robotPositions[kvp.Value];
				robotPositions[kvp.Value] = position;
				
				string fingerprint = robotPositions.Join() + "-" + keysLeft.OrderBy(k => k).Join("");
				
				robotPositions[kvp.Value] = tempRP;

				(int, List<char>) lengthAndPath;

				if (!keysToPath.TryGetValue(fingerprint, out lengthAndPath))
				{
					Map copy = Copy();

					copy.SetRobotPosition(kvp.Value, position);
					copy.TakeKey(kvp.Key);

					List<char> temp = new List<char>();
					copy.FindKeyOrder(out int tempLength, temp);

					lengthAndPath = (tempLength, temp);

					keysToPath[fingerprint] = lengthAndPath;
				}

				int pathLength = lengthAndPath.Item1 + toKeyPath;
				if (pathLength < bestPathLength) {
					path.Clear();
					path.Insert(0, kvp.Key);
					path.AddRange(lengthAndPath.Item2);
					bestPathLength = pathLength;
				}
			}

			level--;
		}
		
		private bool IsDoor(char c) 
		{
			return c >= 'A' && c <= 'Z';	
		}
		
		private bool IsKey(char c) 
		{
			return c >= 'a' && c <= 'z';	
		}

		private Dictionary<char, int> FindReachable(IList<Vec2> source, Func<char, bool> criteria)
		{
			Dictionary<char, int> result = new Dictionary<char, int>();

			for (int i = 0; i < source.Count; i++)
			{
				Vec2 s = source[i];
				Dictionary<char, int> reachable = FindReachable(s, criteria);
				foreach (var kvp in reachable)
				{
					result[kvp.Key] = i;
				}
			}

			return result;
		}

		private Dictionary<char, int> FindReachable(Vec2 source, Func<char, bool> criteria) {
			
			HashSet<Vec2> visited = new HashSet<Vec2>();
			HashSet<Vec2> openSet = new HashSet<Vec2>();
			HashSet<Vec2> newOpenSet = new HashSet<Vec2>();
			openSet.Add(source);
			visited.Add(source);
			int distance = 0;
			
			Dictionary<char, int> result = new Dictionary<char, int>();
			
			while (openSet.Count > 0) {
				
				foreach (Vec2 v in openSet) {
					char c = GetTile(v);
					if (criteria(c))
					{
						if (!result.ContainsKey(c))
						{
							result[c] = distance;
						}
					}
					
					if (!CanWalkOn(c))
						continue;
					
					for (int i = 0; i < 4; ++i) {
						
						Vec2 candidate = v + (Direction)i;
						
						if (visited.Contains(candidate))
							continue;
						
						newOpenSet.Add(candidate);
						visited.Add(candidate);
					}
				}
				
				openSet.Clear();
				openSet.UnionWith(newOpenSet);
				newOpenSet.Clear();
				++distance;
			}
			
			return result;
			
		}
		
		private bool CanWalkOn(char c) {
			if (c == WALL)
				return false;
			
			if (c == EMPTY)
				return true;
			
			if (c >= 'a' && c <= 'z')
				return true;
			
			return false;
		}
			
		public int GetPathLength(Vec2 source, Vec2 target) {
			List<Vec2> path = new List<Vec2>();
			if (!FindPath(source, target, path)) {
				return -1;	
			}
			return path.Count;
		}
				
		public int GetPathLength(Vec2 source, IEnumerable<Vec2> targets) {
			
			List<Vec2> path = new List<Vec2>();
			int result = 0;
			foreach (Vec2 target in targets) {
				if (!FindPath(source, target, path)) {
					return -1;	
				}
				result += path.Count;
				source = target;
			}
			return result;
			
			
		}
						
		public bool FindPath(Vec2 source, Vec2 target, List<Vec2> path) {
			
			path.Clear();
			
			Dictionary<Vec2, Vec2> cameFrom = new Dictionary<Vec2, Vec2>();
			Dictionary<Vec2, int> gScore = new Dictionary<Vec2, int>();
			Dictionary<Vec2, int> fScore = new Dictionary<Vec2, int>();

			HashSet<Vec2> openSet = new HashSet<Vec2>();
			
			openSet.Add(source);
			gScore[source] = 0;
			fScore[source] = source.GetManhattan(target);
			
			int GetGScore(Vec2 v) {
				if (gScore.TryGetValue(v, out int s)) {
					return s;
				}
				return int.MaxValue;
			}
			
			while (openSet.Count > 0) {
				int lScore = int.MaxValue;
				Vec2 current = default;
				foreach (Vec2 v in openSet) {
					if (v.GetManhattan(target) < lScore) {
						current = v;
						lScore = v.GetManhattan(target);
					}
				}
				
				if (current == target) {
					while (true) {
						if (current == source) {
							return true;	
						}
						path.Insert(0, current);	
						current = cameFrom[current];
					}
				}
				
				openSet.Remove(current);
				int gScoreCurrent = GetGScore(current);
				
				for (int i = 0; i < 4; ++i) {
					Direction d = (Direction)i;
					Vec2 neighbour = current + d;
					
					if (!CanWalkOn(GetTile(neighbour)) && neighbour != target)
					{
						continue;
					}
					int tScore = gScoreCurrent + 1;
					if (tScore < GetGScore(neighbour)) {
						cameFrom[neighbour] = current;
						gScore[neighbour] = tScore;
						fScore[neighbour] = tScore + neighbour.GetManhattan(target);
						openSet.Add(neighbour);
					}
				}
			}
			return false;
		}

	}
}	

public static class Extensions {

	public static void Swap<T>(this IList<T> l, int indexA, int indexB) {
		T temp = l[indexA];
		l[indexA] = l[indexB];
		l[indexB] = temp;
	}
	
	public static string Join<T>(this IEnumerable<T> input, string separator = ", ") {
		return string.Join(separator, input);
	}

	public static List<List<T>> GetPermutations<T>(this IEnumerable<T> input) {

		List<T> A = new List<T>(input);
		int n = A.Count;
		//c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k+1, A) is called
		int[] c = new int[n];

		List<List<T>> result = new List<List<T>>();

		result.Add(A.ToList());

		//i acts similarly to the stack pointer
		int i = 0;
		while (i < n) {
			if (c[i] < i) {
				if (i % 2 == 0) {
					A.Swap(0, i);
				} else {
					A.Swap(c[i], i);
				}
				result.Add(A.ToList());
				//Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
				c[i] += 1;
				//Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
				i = 0;
			}
			else {
				//Calling generate(i+1, A) has ended as the for-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
				c[i] = 0;
				i += 1;
			}

		}
		return result;

	}
}

public class Input {

	public static string EXAMPLE1 = @"#########
#b.A.@.a#
#########";

	public static string EXAMPLE2 = @"########################
#f.D.E.e.C.b.A.@.a.B.c.#
######################.#
#d.....................#
########################";

	public static string EXAMPLE3 = @"#############
#g#f.D#..h#l#
#F###e#E###.#
#dCba@#@BcIJ#
#############
#nK.L@#@G...#
#M###N#H###.#
#o#m..#i#jk.#
#############";
	
	public static string EXAMPLE5 = @"########################
#@..............ac.GI.b#
###d#e#f################
###A#B#C################
###g#h#i################
########################";

	public static string INPUT1 = @"#################################################################################
#.......#.A...........#.........#.......#.#.........#.............#...#..r......#
#.###.###.#####.#####.#.#######.#.#######.#.#.#####.#.#.#.#######.###.#.###.###.#
#...#.#...#.....#.#...#...#.....#.......#...#.#...#o#.#.#.#...#.#...#.#...#.#...#
#####.#.###.#####.#.###.#W###.#########.#####.#.#.###.#.#.#.#.#.###.#K###.#.#####
#.....#.#.#...#...#...#.#...#...........#...#...#.....#.#.#.#.#.#...#...#.#.....#
#M###.#.#.###.#.#####.#####.###########.#.#.###.#######.###.#.#.#.#####.#.#####.#
#.#...#...#...#.#...#.....#...#..z....#.#.#...#...#.....#...#.#.#.#...#.......#.#
#.###.###.#.###.#.#.#####.###.#.###.#.#.#.###.#####.#.###.###.#.#.#.#.#####.###.#
#...#...#.#.#....y#.....#.....#.#.#.#.#.#...#.#...#.#.#...#...#.#...#.#...#.#m..#
#.#.#####.#.###########.#######.#.#.#.#.###.#.#.#X#.#.#.###.###.#####.#.#.###.###
#.#.#...#.#s..#.......#.......#...#.#.#.#...#...#.#.#.#.#.#.#.......#...#...#...#
###.#.#.#.###.#.#####.###.###.#####.#.#.#.#######.#.###.#.#.#.#####.#######.###.#
#...#.#...#.#...#...#.#...#.......#.#.#.#.#.......#.....#.#.#.#.....#.....#.....#
#.###.#####.#####.#.#C#.###.#####.#.#.#.#.#####.###.#####.#.###.#####.#.#.#####.#
#.....#.....#.....#.#.#.#...#...#...#.#.#.#.F.#...#...#...#...#.#...#.#.#.....#.#
#.#######.#.###.###.#.#.#####.#.#######.#.#.#.###.###.###.###.#.#.#.#.#.#######.#
#.#.......#...#.#...#.#...#...#.#.......#...#.#.#...#.......#.#.#.#.#.#.........#
#.#.#########.#.#####.###N#.###.#.###########.#.###.#########.#.#.#.#.###########
#...#...#.......#.....#...#.#.#.#.......#...#.#...............#...#.#.#....q....#
#####.###.#######.#####.###.#.#.#######.#.#.#.#############.#####.#.#.#.#.#####.#
#g..#.....#.....#...#.#...#...#.......#.#.#.#..l..........#.#...#.#.#.#.#...#...#
###.#.#####.###.###.#T#.#.###.###.#####.###.#############.#####B#.#.#.#.###.#####
#...#.#...#...#.....#.#.#...#.#.#.#...#.#.......#.......#...#...#.#...#...#.....#
#.###.###.###.#####.#.###.###.#.#.#.#.#.#.#####.#.###.#####.#.###.#####.#######.#
#...#...#...#.#.#...#...#.I...#.#...#...#.....#.#...#.#...#...#.#...#.#.#.......#
###.###.#.###.#.#.#####.#####.#.#############.#####.#.#.#.#####.###.#.#.#.#######
#.....#.#...#.#.......#.#...#...........#.....#.....#...#.......#.#.#.#.#.......#
#.#####.###.#.#######.#.#.#.#####.#######.###.#.###########.###.#.#.#.#.#######.#
#...........#.#e....#.#...#...#...#.....#.#...#...#.........#.....#.#...#.......#
#.###########.#.###.#########.#####.###.#.#######.#.#####.#######.#.#####.#####.#
#.....#.#.....#.#.#.........#.......#...#.#.......#.#.....#.....#.#...#...#.#...#
#####.#.#.#####.#.#####.#.###########.###.#.#######.#####.#.###.#.###.#.###.#.###
#...#.#.#.......#.#.....#.#.........#.#.#...#.#.....#...#.#.#...#...#.#...#...#.#
#.###.#.#########.#.#####.#V#.#####.#.#.#.###.#.###.#.#.###.#.#######.###.#.###.#
#.#...#.....#.....#.#.....#.#...#...#.#.#.#...#.#.#.#.#.....#.........#...#.#...#
#.#.###.###.#.#####.#######.###.#.###.#.#.###.#.#.#.#.#################.###.#.#.#
#.#.....#.#.#.....#.......#.#.#.#...#.#.#.#...#.#...#.#.........#.......#.S.#.#.#
#.#######.#.#####.#######.#.#.#.#####.#.#.#.#.#.#####.#####.###.#.#######.###.#.#
#.......................#.....#.............#.#.............#.....#...........#.#
#######################################.@.#######################################
#...............#.....#.....#.............#.........................D.......#..u#
#.#############.#####.#.#.###.###.#####.#.#.#.#####.#######.###############.#.###
#.....#.....#...#...#...#.....#.#.#.....#...#....v#.#.....#.#.......#.....#.#.E.#
#####.#.#####.###.#.#.#########.#.#######.#######.###.###.###.#####.#.#####.#.#.#
#.....#.....#.....#.#.#...#.....#.......#.#.......#.....#.#...#...#.#....j#t#.#.#
#.#########.#######.#.#.#.#.###########.#.#.#######.#####.#.###.###.#####.#.#.#.#
#.......#...#...#...#...#...#.......#...#.#.#.....#.#.....#.#.....#.#...#.#.#.#.#
#######.#.#.###.#.#######.###.#####.#.#####.#.###.#.#.#####.#####.#.#.#.#.#.###.#
#.....#.#.#.....#...#.....#...#.....#...#...#.#.#...#.....#.......#...#.#.#.#...#
###.###.#.#####.###.#####.#.###.#####.#.#.#.#.#.#########.#######.#####.#.#.#.#.#
#...#...#...#...#.#.....#.#.#.#.#.....#.#.#d#.#.....#.......#.....#.....#.#...#.#
#.###.#####.#.###.#####.#.#.#.#.#######.#.###.###.#.#.#######.#####.#####.#####.#
#.....#...#.#.....#.....#.#.#.#...#.....#.....#...#.#.....#.....#...#...#.....#.#
#.#####.#.#.#.#####.#####.#.#.###.#.###.#######.#.#######.#.#####.#####.#.#.#.#.#
#.#.....#.#.#.#.....#.....#.#...#.#.#...#.......#.#.....#...#.#...#.....#.#.#.#.#
#.###.#.#.#.#.#.###########.###.#.#.#.###.#########.#.#######.#.#####.###.#.###.#
#.H.#.#.#.#.#.#.....#.....#.#...#...#...#.#.....#...#.........#.#.....#...#.....#
###.###.#.#.#.#####.#.###.#.#.#########.#.#.###.#.#######.#####.#.#.#.#.#########
#.#.#...#...#...#.#...#...#.#...#.......#...#.#...#.....#...#...#.#.#.#.........#
#.#.#.#.#######.#.#####.###.#.#.#.#######.###.#########.###.#.#####.#.#########.#
#...#.#.#...#.#.#...#...#...#.#.#...#...#...#...#.....#...#.#.#.....#.#.......#.#
#.###.###.#.#.#.###.#######.#.#.###.#.#.###.#.###.#.#.#.#.#.###.#####.###.###.#.#
#.#...#...#.#.#.#...........#.#...#.#.#.#.#.#.#...#.#...#.#.....#...#...#.#.#.#.#
#.###.#.###.#.#.#.###########.###.#.#.#.#.#.#.#.###.#####.#####.###.###.#.#.#.#.#
#...#...#.#.#.#...#...#.U...#.#.#...#.#.#...#.....#.#.....#...#...#...#...#...#.#
###.#.###.#.#.#####J#.#.#.###.#.#####.###.#######.#.#####.#.#####.#.#####.#####.#
#...#.Q.#.#.#.....#.#...#.....#.........#.......#.#f....#.L.#.....#h....#.#...#.#
#.#####.#.#.###.#.#.#################.#.#######.#.#####.###.#.#####.#.###.#.#.#.#
#.#...#...#...#.#.#.#...#.......#...#.#.#.#...G.#.....#.Z.#.#...#...#.....#.#...#
#.#.#####.###.###.#.#.#.#####.#.#.#.###.#.#.#############.#.###.#########.#.#####
#k#.#.....#.#...#.#..c#...#...#...#.#...#.#.#........n#...#...#.#.......#.#...#.#
#.#.#.#####.###.#.#######.#.#######.#.#.#.#.#.#######.#.###.###.#.#####.#####.#.#
#.#...#.....#...#.#.P...#.#.#.....#...#.#.#.#.#...#...#.#...#...#.....#.....#p..#
#.###.#.#.###.###.#.#.###.#.###.#.#####.#.#.#.#.###.###.###.#.#######.###.#####.#
#...#...#.#...#.#...#...#.#...#.#...#...#.O.#.#.....#.#...#b#.#.......#.#.#...#.#
###.#####.#.###.#.#####.#.###.#####.#.###.###.#.#####.#.#.###.#.#######.#.#.#.#.#
#.#.#.....#.#a..#.#...#.#.#...#.....#...#...#i#.#...#...#.Y.#.#.#....w..#.#.#...#
#.#R#######.#.#.#.###.#.#.#.###.#######.###.#.#.#.#.#######.#.#.#####.#.#.#.#####
#...........#.#.......#.....#...........#.....#x..#.........#.........#.#.......#
#################################################################################";
	
	
	public static string INPUT2 = @"#################################################################################
#.......#.A...........#.........#.......#.#.........#.............#...#..r......#
#.###.###.#####.#####.#.#######.#.#######.#.#.#####.#.#.#.#######.###.#.###.###.#
#...#.#...#.....#.#...#...#.....#.......#...#.#...#o#.#.#.#...#.#...#.#...#.#...#
#####.#.###.#####.#.###.#W###.#########.#####.#.#.###.#.#.#.#.#.###.#K###.#.#####
#.....#.#.#...#...#...#.#...#...........#...#...#.....#.#.#.#.#.#...#...#.#.....#
#M###.#.#.###.#.#####.#####.###########.#.#.###.#######.###.#.#.#.#####.#.#####.#
#.#...#...#...#.#...#.....#...#..z....#.#.#...#...#.....#...#.#.#.#...#.......#.#
#.###.###.#.###.#.#.#####.###.#.###.#.#.#.###.#####.#.###.###.#.#.#.#.#####.###.#
#...#...#.#.#....y#.....#.....#.#.#.#.#.#...#.#...#.#.#...#...#.#...#.#...#.#m..#
#.#.#####.#.###########.#######.#.#.#.#.###.#.#.#X#.#.#.###.###.#####.#.#.###.###
#.#.#...#.#s..#.......#.......#...#.#.#.#...#...#.#.#.#.#.#.#.......#...#...#...#
###.#.#.#.###.#.#####.###.###.#####.#.#.#.#######.#.###.#.#.#.#####.#######.###.#
#...#.#...#.#...#...#.#...#.......#.#.#.#.#.......#.....#.#.#.#.....#.....#.....#
#.###.#####.#####.#.#C#.###.#####.#.#.#.#.#####.###.#####.#.###.#####.#.#.#####.#
#.....#.....#.....#.#.#.#...#...#...#.#.#.#.F.#...#...#...#...#.#...#.#.#.....#.#
#.#######.#.###.###.#.#.#####.#.#######.#.#.#.###.###.###.###.#.#.#.#.#.#######.#
#.#.......#...#.#...#.#...#...#.#.......#...#.#.#...#.......#.#.#.#.#.#.........#
#.#.#########.#.#####.###N#.###.#.###########.#.###.#########.#.#.#.#.###########
#...#...#.......#.....#...#.#.#.#.......#...#.#...............#...#.#.#....q....#
#####.###.#######.#####.###.#.#.#######.#.#.#.#############.#####.#.#.#.#.#####.#
#g..#.....#.....#...#.#...#...#.......#.#.#.#..l..........#.#...#.#.#.#.#...#...#
###.#.#####.###.###.#T#.#.###.###.#####.###.#############.#####B#.#.#.#.###.#####
#...#.#...#...#.....#.#.#...#.#.#.#...#.#.......#.......#...#...#.#...#...#.....#
#.###.###.###.#####.#.###.###.#.#.#.#.#.#.#####.#.###.#####.#.###.#####.#######.#
#...#...#...#.#.#...#...#.I...#.#...#...#.....#.#...#.#...#...#.#...#.#.#.......#
###.###.#.###.#.#.#####.#####.#.#############.#####.#.#.#.#####.###.#.#.#.#######
#.....#.#...#.#.......#.#...#...........#.....#.....#...#.......#.#.#.#.#.......#
#.#####.###.#.#######.#.#.#.#####.#######.###.#.###########.###.#.#.#.#.#######.#
#...........#.#e....#.#...#...#...#.....#.#...#...#.........#.....#.#...#.......#
#.###########.#.###.#########.#####.###.#.#######.#.#####.#######.#.#####.#####.#
#.....#.#.....#.#.#.........#.......#...#.#.......#.#.....#.....#.#...#...#.#...#
#####.#.#.#####.#.#####.#.###########.###.#.#######.#####.#.###.#.###.#.###.#.###
#...#.#.#.......#.#.....#.#.........#.#.#...#.#.....#...#.#.#...#...#.#...#...#.#
#.###.#.#########.#.#####.#V#.#####.#.#.#.###.#.###.#.#.###.#.#######.###.#.###.#
#.#...#.....#.....#.#.....#.#...#...#.#.#.#...#.#.#.#.#.....#.........#...#.#...#
#.#.###.###.#.#####.#######.###.#.###.#.#.###.#.#.#.#.#################.###.#.#.#
#.#.....#.#.#.....#.......#.#.#.#...#.#.#.#...#.#...#.#.........#.......#.S.#.#.#
#.#######.#.#####.#######.#.#.#.#####.#.#.#.#.#.#####.#####.###.#.#######.###.#.#
#.......................#.....#........@#@..#.#.............#.....#...........#.#
#################################################################################
#...............#.....#.....#..........@#@#.........................D.......#..u#
#.#############.#####.#.#.###.###.#####.#.#.#.#####.#######.###############.#.###
#.....#.....#...#...#...#.....#.#.#.....#...#....v#.#.....#.#.......#.....#.#.E.#
#####.#.#####.###.#.#.#########.#.#######.#######.###.###.###.#####.#.#####.#.#.#
#.....#.....#.....#.#.#...#.....#.......#.#.......#.....#.#...#...#.#....j#t#.#.#
#.#########.#######.#.#.#.#.###########.#.#.#######.#####.#.###.###.#####.#.#.#.#
#.......#...#...#...#...#...#.......#...#.#.#.....#.#.....#.#.....#.#...#.#.#.#.#
#######.#.#.###.#.#######.###.#####.#.#####.#.###.#.#.#####.#####.#.#.#.#.#.###.#
#.....#.#.#.....#...#.....#...#.....#...#...#.#.#...#.....#.......#...#.#.#.#...#
###.###.#.#####.###.#####.#.###.#####.#.#.#.#.#.#########.#######.#####.#.#.#.#.#
#...#...#...#...#.#.....#.#.#.#.#.....#.#.#d#.#.....#.......#.....#.....#.#...#.#
#.###.#####.#.###.#####.#.#.#.#.#######.#.###.###.#.#.#######.#####.#####.#####.#
#.....#...#.#.....#.....#.#.#.#...#.....#.....#...#.#.....#.....#...#...#.....#.#
#.#####.#.#.#.#####.#####.#.#.###.#.###.#######.#.#######.#.#####.#####.#.#.#.#.#
#.#.....#.#.#.#.....#.....#.#...#.#.#...#.......#.#.....#...#.#...#.....#.#.#.#.#
#.###.#.#.#.#.#.###########.###.#.#.#.###.#########.#.#######.#.#####.###.#.###.#
#.H.#.#.#.#.#.#.....#.....#.#...#...#...#.#.....#...#.........#.#.....#...#.....#
###.###.#.#.#.#####.#.###.#.#.#########.#.#.###.#.#######.#####.#.#.#.#.#########
#.#.#...#...#...#.#...#...#.#...#.......#...#.#...#.....#...#...#.#.#.#.........#
#.#.#.#.#######.#.#####.###.#.#.#.#######.###.#########.###.#.#####.#.#########.#
#...#.#.#...#.#.#...#...#...#.#.#...#...#...#...#.....#...#.#.#.....#.#.......#.#
#.###.###.#.#.#.###.#######.#.#.###.#.#.###.#.###.#.#.#.#.#.###.#####.###.###.#.#
#.#...#...#.#.#.#...........#.#...#.#.#.#.#.#.#...#.#...#.#.....#...#...#.#.#.#.#
#.###.#.###.#.#.#.###########.###.#.#.#.#.#.#.#.###.#####.#####.###.###.#.#.#.#.#
#...#...#.#.#.#...#...#.U...#.#.#...#.#.#...#.....#.#.....#...#...#...#...#...#.#
###.#.###.#.#.#####J#.#.#.###.#.#####.###.#######.#.#####.#.#####.#.#####.#####.#
#...#.Q.#.#.#.....#.#...#.....#.........#.......#.#f....#.L.#.....#h....#.#...#.#
#.#####.#.#.###.#.#.#################.#.#######.#.#####.###.#.#####.#.###.#.#.#.#
#.#...#...#...#.#.#.#...#.......#...#.#.#.#...G.#.....#.Z.#.#...#...#.....#.#...#
#.#.#####.###.###.#.#.#.#####.#.#.#.###.#.#.#############.#.###.#########.#.#####
#k#.#.....#.#...#.#..c#...#...#...#.#...#.#.#........n#...#...#.#.......#.#...#.#
#.#.#.#####.###.#.#######.#.#######.#.#.#.#.#.#######.#.###.###.#.#####.#####.#.#
#.#...#.....#...#.#.P...#.#.#.....#...#.#.#.#.#...#...#.#...#...#.....#.....#p..#
#.###.#.#.###.###.#.#.###.#.###.#.#####.#.#.#.#.###.###.###.#.#######.###.#####.#
#...#...#.#...#.#...#...#.#...#.#...#...#.O.#.#.....#.#...#b#.#.......#.#.#...#.#
###.#####.#.###.#.#####.#.###.#####.#.###.###.#.#####.#.#.###.#.#######.#.#.#.#.#
#.#.#.....#.#a..#.#...#.#.#...#.....#...#...#i#.#...#...#.Y.#.#.#....w..#.#.#...#
#.#R#######.#.#.#.###.#.#.#.###.#######.###.#.#.#.#.#######.#.#.#####.#.#.#.#####
#...........#.#.......#.....#...........#.....#x..#.........#.........#.#.......#
#################################################################################";
}

​x
 
using System;
using System.Linq;
using System.Collections.Generic;
public class Program
{
    
    public static void Main()
    {   
        Map map = new Map(Input.INPUT2);
        List<char> keys = new List<char>();
        
        int pathLength = 0;
        map.FindKeyOrder(out pathLength, keys);
                
        Console.WriteLine("Keys: " + string.Join(",", keys));
        Console.WriteLine("Distance: " + pathLength);
        
    }
    
    public enum Direction {
        None = -1,
        East = 0,
        North = 1,
        West = 2,
        South = 3,
    }
    
    public struct Vec2 : IEquatable<Vec2> {
        public int x, y;    
        
        public Vec2(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        public static Vec2 operator+(Vec2 a, Vec2 b) {
            return new Vec2() { x = a.x + b.x, y = a.y + b.y };
        }   
        
        public static Vec2 operator+(Vec2 v, Direction dir) {
            switch (dir) {
                case Direction.North:
                    v.y -= 1;
                    break;
                case Direction.South:
                    v.y += 1;
                    break;
                case Direction.West:
                    v.x -= 1;
                    break;
                case Direction.East:
                    v.x += 1;
                    break;
            }
            return v;
        }
        
        public Direction GetDirection(Vec2 other) {
            if (other.x == x && other.y == y)
                return Direction.None;
            
            if (Math.Abs(other.x - x) > Math.Abs(other.y - y)) {
                if (other.x > x)
                    return Direction.East;
                return Direction.West;
            }
            else {
                if (other.y > y)
                    return Direction.South;
                return Direction.North;
            }
            
        }
        
        public int GetManhattan(Vec2 other) {
            return Math.Abs(x - other.x) + Math.Abs(y - other.y);   
        }
        
        public static bool operator==(Vec2 a, Vec2 b) {
            return a.x == b.x && a.y == b.y;    
        }
        
        public static bool operator!=(Vec2 a, Vec2 b) {
            return a.x != b.x || a.y != b.y;    
        }
        
        public override string ToString() {
            return "(" + x + ", " + y + ")";    
        }
        
        public override int GetHashCode()
        {
            return x.GetHashCode() ^ (y.GetHashCode() << 2);
        }
        
        public override bool Equals(object o) {
            Vec2 other = (Vec2)o;
            return other.x == x && other.y == y;
        }
        public bool Equals(Vec2 other) {
            return other.x == x && other.y == y;
        }
    }
    
    public class Map {
        
        public const char UNKNOWN = (char)0;
        public const char EMPTY = '.';
        public const char WALL = '#';
        
        private List<Vec2> robotPositions = new List<Vec2>();
        private char[] tiles;
        private Vec2 offset;
        private Vec2 size;
        private Dictionary<char, Vec2> keys = new Dictionary<char, Vec2>();
        private Dictionary<char, Vec2> doors = new Dictionary<char, Vec2>();
        
        public Map Copy() {
            Map result = new Map();
            
            result.robotPositions.AddRange(robotPositions);
            result.tiles = new char[tiles.Length];
            Array.Copy(tiles, result.tiles, tiles.Length);
            
            result.offset = offset;
            result.size = size;
            
            result.keys = new Dictionary<char, Vec2>(keys);
            result.doors = new Dictionary<char, Vec2>(doors);
            
            return result;          
        }
        
        private Map() {
        }
        
        public Map(string input)
        {
            Vec2 pos = new Vec2(0, 0);
            for (int i = 0; i < input.Length; ++i) {
                char c = input[i];
                if (c == '\n') {
                    pos.y ++;
                    pos.x = 0;
                    continue;
                }
                if (c == '@') {
                    robotPositions.Add(pos);    
                    SetTile(pos, '.');
                }
                else {
                    SetTile(pos, c);    
                }
                
                pos.x++;
            }
        }
        
        public void SetRobotPosition(int index, Vec2 position) {
            robotPositions[index] = position;   
            AddPosition(position);
        }
        
        public void SetTile(Vec2 position, char tile) {
            AddPosition(position);
            
            if (IsDoor(tile)) {
                doors[tile] = position; 
            }
            
            if (IsKey(tile)) {
                keys[tile] = position;  
            }
            
            tiles[position.x - offset.x + (position.y - offset.y) * size.x] = tile;
        }
        
        public char GetTile(Vec2 position) {
            position.x -= offset.x;
            position.y -= offset.y;
            
            if (position.x < 0 || position.y < 0)
                return UNKNOWN;
            
            if (position.x >= size.x || position.y >= size.y)
                return UNKNOWN;
            
            return tiles[position.x + position.y * size.x];
        }
        
        public Vec2 GetPosition(char c) {
            if (keys.ContainsKey(c))
                return keys[c];
            
            if (doors.ContainsKey(c))
                return doors[c];
            
            throw new Exception(c + " not found in map");
        }
        
        private void AddPosition(Vec2 newPosition) {
            int newOffsetX = Math.Min(newPosition.x, offset.x);
            int newOffsetY = Math.Min(newPosition.y, offset.y);
            
            int newWidth = Math.Max(newPosition.x - newOffsetX + 1, size.x - newOffsetX + offset.x);
            int newHeight = Math.Max(newPosition.y - newOffsetY + 1, size.y - newOffsetY + offset.y);
            
            if (size.x >= newWidth && size.y >= newHeight && newOffsetX >= offset.x && newOffsetY >= offset.y)
                return;
            
            char[] newTiles = new char[newWidth * newHeight];
            if (tiles != null) {
                for (int y = 0; y < size.y; ++y) {
                    for (int x = 0; x < size.x; ++x) {  
                        newTiles[x + offset.x - newOffsetX + (y + offset.y - newOffsetY) * newWidth] = tiles[x + y * size.x];
                    }
                }
            }   
            offset.x = newOffsetX;
            offset.y = newOffsetY;
            tiles = newTiles;
            size.x = newWidth;
            size.y = newHeight;
        }
        
        public void Display() 
        {
            for (int y = 0; y < size.y; ++y) {
                for (int x = 0; x < size.x; ++x)
                {
                    bool drawRobot = false;
                    foreach (Vec2 robotPosition in robotPositions)
                    {
                        if ((robotPosition.x - offset.x) == x && (robotPosition.y - offset.y) == y) {
                            Console.Write("@");
                            drawRobot = true;
                            break;
                        }
                    }
                    
                    if (drawRobot)
                        continue;
                    
                    char c = tiles[x + y * size.x];
                    
                    if (c == 0)
                        c = ' ';
                    Console.Write(c);
                }
                Console.WriteLine();
            }
        }
        
        public void TakeKey(char c) {
            if (!IsKey(c))
                throw new Exception(c + " is not a key");
            
            SetTile(keys[c], '.');
            keys.Remove(c);
            
            char door = char.ToUpper(c);
            if (Exists(door)) {
                OpenDoor(door); 
            }
        }
        
        public bool Exists(char c) {
            return keys.ContainsKey(c) || doors.ContainsKey(c); 
        }
        
        public void OpenDoor(char c) {
            if (!IsDoor(c))
                throw new Exception(c + " is not a key");
            
            SetTile(doors[c], '.');
            doors.Remove(c);
        }
        
        private static Dictionary<string, (int, List<char>)> keysToPath
            = new Dictionary<string, (int, List<char>)>();
​
        private static int level = 0;
        
        public void FindKeyOrder(out int bestPathLength, List<char> path) {
​
            if (keys.Count == 0)
            {
                bestPathLength = 0;
                return;
            }
​
            level++;
            
            var reachable = FindReachable(robotPositions, IsKey);
                        
            bestPathLength = int.MaxValue;
            
            foreach (var kvp in reachable)
            {
                if (level < 2)
                {
                    Console.WriteLine("Starting with key " + kvp.Key);
                }
                Vec2 position = GetPosition(kvp.Key);
                int toKeyPath = GetPathLength(robotPositions[kvp.Value], position);
​
                HashSet<char> keysLeft = new HashSet<char>(keys.Keys);
                keysLeft.Remove(kvp.Key);
​
                Vec2 tempRP = robotPositions[kvp.Value];
                robotPositions[kvp.Value] = position;
                
                string fingerprint = robotPositions.Join() + "-" + keysLeft.OrderBy(k => k).Join("");
                
                robotPositions[kvp.Value] = tempRP;
​
                (int, List<char>) lengthAndPath;
​
                if (!keysToPath.TryGetValue(fingerprint, out lengthAndPath))
                {
                    Map copy = Copy();
​
                    copy.SetRobotPosition(kvp.Value, position);
                    copy.TakeKey(kvp.Key);
​
                    List<char> temp = new List<char>();
                    copy.FindKeyOrder(out int tempLength, temp);
​
                    lengthAndPath = (tempLength, temp);
​
                    keysToPath[fingerprint] = lengthAndPath;
                }
​
                int pathLength = lengthAndPath.Item1 + toKeyPath;
                if (pathLength < bestPathLength) {
                    path.Clear();
                    path.Insert(0, kvp.Key);
                    path.AddRange(lengthAndPath.Item2);
                    bestPathLength = pathLength;
                }
            }
​
            level--;
        }
        
        private bool IsDoor(char c) 
        {
            return c >= 'A' && c <= 'Z';    
        }
        
        private bool IsKey(char c) 
        {
            return c >= 'a' && c <= 'z';    
        }
​
        private Dictionary<char, int> FindReachable(IList<Vec2> source, Func<char, bool> criteria)
        {
            Dictionary<char, int> result = new Dictionary<char, int>();
​
            for (int i = 0; i < source.Count; i++)
            {
                Vec2 s = source[i];
                Dictionary<char, int> reachable = FindReachable(s, criteria);
                foreach (var kvp in reachable)
                {
                    result[kvp.Key] = i;
                }
            }
​
            return result;
        }
​
        private Dictionary<char, int> FindReachable(Vec2 source, Func<char, bool> criteria) {
            
            HashSet<Vec2> visited = new HashSet<Vec2>();
            HashSet<Vec2> openSet = new HashSet<Vec2>();
            HashSet<Vec2> newOpenSet = new HashSet<Vec2>();
            openSet.Add(source);
            visited.Add(source);
            int distance = 0;
            
            Dictionary<char, int> result = new Dictionary<char, int>();
            
            while (openSet.Count > 0) {
                
                foreach (Vec2 v in openSet) {
                    char c = GetTile(v);
                    if (criteria(c))
                    {
                        if (!result.ContainsKey(c))
                        {
                            result[c] = distance;
                        }
                    }
                    
                    if (!CanWalkOn(c))
                        continue;
                    
                    for (int i = 0; i < 4; ++i) {
                        
                        Vec2 candidate = v + (Direction)i;
                        
                        if (visited.Contains(candidate))
                            continue;
                        
                        newOpenSet.Add(candidate);
                        visited.Add(candidate);
                    }
                }
                
                openSet.Clear();
                openSet.UnionWith(newOpenSet);
                newOpenSet.Clear();
                ++distance;
            }
            
            return result;
            
        }
        
        private bool CanWalkOn(char c) {
            if (c == WALL)
                return false;
            
            if (c == EMPTY)
                return true;
            
            if (c >= 'a' && c <= 'z')
                return true;
            
            return false;
        }
            
        public int GetPathLength(Vec2 source, Vec2 target) {
            List<Vec2> path = new List<Vec2>();
            if (!FindPath(source, target, path)) {
                return -1;  
            }
            return path.Count;
        }
                
        public int GetPathLength(Vec2 source, IEnumerable<Vec2> targets) {
            
            List<Vec2> path = new List<Vec2>();
            int result = 0;
            foreach (Vec2 target in targets) {
                if (!FindPath(source, target, path)) {
                    return -1;  
                }
                result += path.Count;
                source = target;
            }
            return result;
            
            
        }
                        
        public bool FindPath(Vec2 source, Vec2 target, List<Vec2> path) {
            
            path.Clear();
            
            Dictionary<Vec2, Vec2> cameFrom = new Dictionary<Vec2, Vec2>();
            Dictionary<Vec2, int> gScore = new Dictionary<Vec2, int>();
            Dictionary<Vec2, int> fScore = new Dictionary<Vec2, int>();
​
            HashSet<Vec2> openSet = new HashSet<Vec2>();
            
            openSet.Add(source);
            gScore[source] = 0;
            fScore[source] = source.GetManhattan(target);
            
            int GetGScore(Vec2 v) {
                if (gScore.TryGetValue(v, out int s)) {
                    return s;
                }
                return int.MaxValue;
            }
            
            while (openSet.Count > 0) {
                int lScore = int.MaxValue;
                Vec2 current = default;
                foreach (Vec2 v in openSet) {
                    if (v.GetManhattan(target) < lScore) {
                        current = v;
                        lScore = v.GetManhattan(target);
                    }
                }
                
                if (current == target) {
                    while (true) {
                        if (current == source) {
                            return true;    
                        }
                        path.Insert(0, current);    
                        current = cameFrom[current];
                    }
                }
                
                openSet.Remove(current);
                int gScoreCurrent = GetGScore(current);
                
                for (int i = 0; i < 4; ++i) {
                    Direction d = (Direction)i;
                    Vec2 neighbour = current + d;
                    
                    if (!CanWalkOn(GetTile(neighbour)) && neighbour != target)
                    {
                        continue;
                    }
                    int tScore = gScoreCurrent + 1;
                    if (tScore < GetGScore(neighbour)) {
                        cameFrom[neighbour] = current;
                        gScore[neighbour] = tScore;
                        fScore[neighbour] = tScore + neighbour.GetManhattan(target);
                        openSet.Add(neighbour);
                    }
                }
            }
            return false;
        }
​
    }
}   
​
public static class Extensions {
​
    public static void Swap<T>(this IList<T> l, int indexA, int indexB) {
        T temp = l[indexA];
        l[indexA] = l[indexB];
        l[indexB] = temp;
    }
    
    public static string Join<T>(this IEnumerable<T> input, string separator = ", ") {
        return string.Join(separator, input);
    }
​
    public static List<List<T>> GetPermutations<T>(this IEnumerable<T> input) {
​
        List<T> A = new List<T>(input);
        int n = A.Count;
        //c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k+1, A) is called
        int[] c = new int[n];
​
        List<List<T>> result = new List<List<T>>();
​
        result.Add(A.ToList());
​
        //i acts similarly to the stack pointer
        int i = 0;
        while (i < n) {
            if (c[i] < i) {
                if (i % 2 == 0) {
                    A.Swap(0, i);
                } else {
                    A.Swap(c[i], i);
                }
                result.Add(A.ToList());
                //Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
                c[i] += 1;
                //Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
                i = 0;
            }
            else {
                //Calling generate(i+1, A) has ended as the for-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
                c[i] = 0;
                i += 1;
            }
​
        }
        return result;
​
    }
}
​
public class Input {
​
    public static string EXAMPLE1 = @"#########
#b.A.@.a#
#########";
​
    public static string EXAMPLE2 = @"########################
#f.D.E.e.C.b.A.@.a.B.c.#
######################.#
#d.....................#
########################";
​
    public static string EXAMPLE3 = @"#############
#g#f.D#..h#l#
#F###e#E###.#
#dCba@#@BcIJ#
#############
#nK.L@#@G...#
#M###N#H###.#
#o#m..#i#jk.#
#############";
    
    public static string EXAMPLE5 = @"########################
#@..............ac.GI.b#
###d#e#f################
###A#B#C################
###g#h#i################
########################";
​
    public static string INPUT1 = @"#################################################################################
#.......#.A...........#.........#.......#.#.........#.............#...#..r......#
#.###.###.#####.#####.#.#######.#.#######.#.#.#####.#.#.#.#######.###.#.###.###.#
#...#.#...#.....#.#...#...#.....#.......#...#.#...#o#.#.#.#...#.#...#.#...#.#...#
#####.#.###.#####.#.###.#W###.#########.#####.#.#.###.#.#.#.#.#.###.#K###.#.#####
#.....#.#.#...#...#...#.#...#...........#...#...#.....#.#.#.#.#.#...#...#.#.....#
#M###.#.#.###.#.#####.#####.###########.#.#.###.#######.###.#.#.#.#####.#.#####.#
#.#...#...#...#.#...#.....#...#..z....#.#.#...#...#.....#...#.#.#.#...#.......#.#
#.###.###.#.###.#.#.#####.###.#.###.#.#.#.###.#####.#.###.###.#.#.#.#.#####.###.#
#...#...#.#.#....y#.....#.....#.#.#.#.#.#...#.#...#.#.#...#...#.#...#.#...#.#m..#
#.#.#####.#.###########.#######.#.#.#.#.###.#.#.#X#.#.#.###.###.#####.#.#.###.###
#.#.#...#.#s..#.......#.......#...#.#.#.#...#...#.#.#.#.#.#.#.......#...#...#...#
###.#.#.#.###.#.#####.###.###.#####.#.#.#.#######.#.###.#.#.#.#####.#######.###.#
#...#.#...#.#...#...#.#...#.......#.#.#.#.#.......#.....#.#.#.#.....#.....#.....#
#.###.#####.#####.#.#C#.###.#####.#.#.#.#.#####.###.#####.#.###.#####.#.#.#####.#
#.....#.....#.....#.#.#.#...#...#...#.#.#.#.F.#...#...#...#...#.#...#.#.#.....#.#
#.#######.#.###.###.#.#.#####.#.#######.#.#.#.###.###.###.###.#.#.#.#.#.#######.#
#.#.......#...#.#...#.#...#...#.#.......#...#.#.#...#.......#.#.#.#.#.#.........#
#.#.#########.#.#####.###N#.###.#.###########.#.###.#########.#.#.#.#.###########
#...#...#.......#.....#...#.#.#.#.......#...#.#...............#...#.#.#....q....#
#####.###.#######.#####.###.#.#.#######.#.#.#.#############.#####.#.#.#.#.#####.#
#g..#.....#.....#...#.#...#...#.......#.#.#.#..l..........#.#...#.#.#.#.#...#...#
###.#.#####.###.###.#T#.#.###.###.#####.###.#############.#####B#.#.#.#.###.#####
#...#.#...#...#.....#.#.#...#.#.#.#...#.#.......#.......#...#...#.#...#...#.....#
#.###.###.###.#####.#.###.###.#.#.#.#.#.#.#####.#.###.#####.#.###.#####.#######.#
#...#...#...#.#.#...#...#.I...#.#...#...#.....#.#...#.#...#...#.#...#.#.#.......#
###.###.#.###.#.#.#####.#####.#.#############.#####.#.#.#.#####.###.#.#.#.#######
#.....#.#...#.#.......#.#...#...........#.....#.....#...#.......#.#.#.#.#.......#
#.#####.###.#.#######.#.#.#.#####.#######.###.#.###########.###.#.#.#.#.#######.#
#...........#.#e....#.#...#...#...#.....#.#...#...#.........#.....#.#...#.......#
#.###########.#.###.#########.#####.###.#.#######.#.#####.#######.#.#####.#####.#
#.....#.#.....#.#.#.........#.......#...#.#.......#.#.....#.....#.#...#...#.#...#
#####.#.#.#####.#.#####.#.###########.###.#.#######.#####.#.###.#.###.#.###.#.###
#...#.#.#.......#.#.....#.#.........#.#.#...#.#.....#...#.#.#...#...#.#...#...#.#
#.###.#.#########.#.#####.#V#.#####.#.#.#.###.#.###.#.#.###.#.#######.###.#.###.#
#.#...#.....#.....#.#.....#.#...#...#.#.#.#...#.#.#.#.#.....#.........#...#.#...#
#.#.###.###.#.#####.#######.###.#.###.#.#.###.#.#.#.#.#################.###.#.#.#
#.#.....#.#.#.....#.......#.#.#.#...#.#.#.#...#.#...#.#.........#.......#.S.#.#.#
#.#######.#.#####.#######.#.#.#.#####.#.#.#.#.#.#####.#####.###.#.#######.###.#.#
#.......................#.....#.............#.#.............#.....#...........#.#
#######################################.@.#######################################
#...............#.....#.....#.............#.........................D.......#..u#
#.#############.#####.#.#.###.###.#####.#.#.#.#####.#######.###############.#.###
#.....#.....#...#...#...#.....#.#.#.....#...#....v#.#.....#.#.......#.....#.#.E.#
#####.#.#####.###.#.#.#########.#.#######.#######.###.###.###.#####.#.#####.#.#.#
#.....#.....#.....#.#.#...#.....#.......#.#.......#.....#.#...#...#.#....j#t#.#.#
#.#########.#######.#.#.#.#.###########.#.#.#######.#####.#.###.###.#####.#.#.#.#
#.......#...#...#...#...#...#.......#...#.#.#.....#.#.....#.#.....#.#...#.#.#.#.#
#######.#.#.###.#.#######.###.#####.#.#####.#.###.#.#.#####.#####.#.#.#.#.#.###.#
#.....#.#.#.....#...#.....#...#.....#...#...#.#.#...#.....#.......#...#.#.#.#...#
###.###.#.#####.###.#####.#.###.#####.#.#.#.#.#.#########.#######.#####.#.#.#.#.#
#...#...#...#...#.#.....#.#.#.#.#.....#.#.#d#.#.....#.......#.....#.....#.#...#.#
#.###.#####.#.###.#####.#.#.#.#.#######.#.###.###.#.#.#######.#####.#####.#####.#
#.....#...#.#.....#.....#.#.#.#...#.....#.....#...#.#.....#.....#...#...#.....#.#
#.#####.#.#.#.#####.#####.#.#.###.#.###.#######.#.#######.#.#####.#####.#.#.#.#.#
#.#.....#.#.#.#.....#.....#.#...#.#.#...#.......#.#.....#...#.#...#.....#.#.#.#.#
#.###.#.#.#.#.#.###########.###.#.#.#.###.#########.#.#######.#.#####.###.#.###.#
#.H.#.#.#.#.#.#.....#.....#.#...#...#...#.#.....#...#.........#.#.....#...#.....#
###.###.#.#.#.#####.#.###.#.#.#########.#.#.###.#.#######.#####.#.#.#.#.#########
#.#.#...#...#...#.#...#...#.#...#.......#...#.#...#.....#...#...#.#.#.#.........#
#.#.#.#.#######.#.#####.###.#.#.#.#######.###.#########.###.#.#####.#.#########.#
#...#.#.#...#.#.#...#...#...#.#.#...#...#...#...#.....#...#.#.#.....#.#.......#.#
#.###.###.#.#.#.###.#######.#.#.###.#.#.###.#.###.#.#.#.#.#.###.#####.###.###.#.#
#.#...#...#.#.#.#...........#.#...#.#.#.#.#.#.#...#.#...#.#.....#...#...#.#.#.#.#
#.###.#.###.#.#.#.###########.###.#.#.#.#.#.#.#.###.#####.#####.###.###.#.#.#.#.#
#...#...#.#.#.#...#...#.U...#.#.#...#.#.#...#.....#.#.....#...#...#...#...#...#.#
###.#.###.#.#.#####J#.#.#.###.#.#####.###.#######.#.#####.#.#####.#.#####.#####.#
#...#.Q.#.#.#.....#.#...#.....#.........#.......#.#f....#.L.#.....#h....#.#...#.#
#.#####.#.#.###.#.#.#################.#.#######.#.#####.###.#.#####.#.###.#.#.#.#
#.#...#...#...#.#.#.#...#.......#...#.#.#.#...G.#.....#.Z.#.#...#...#.....#.#...#
#.#.#####.###.###.#.#.#.#####.#.#.#.###.#.#.#############.#.###.#########.#.#####
#k#.#.....#.#...#.#..c#...#...#...#.#...#.#.#........n#...#...#.#.......#.#...#.#
#.#.#.#####.###.#.#######.#.#######.#.#.#.#.#.#######.#.###.###.#.#####.#####.#.#
#.#...#.....#...#.#.P...#.#.#.....#...#.#.#.#.#...#...#.#...#...#.....#.....#p..#
#.###.#.#.###.###.#.#.###.#.###.#.#####.#.#.#.#.###.###.###.#.#######.###.#####.#
#...#...#.#...#.#...#...#.#...#.#...#...#.O.#.#.....#.#...#b#.#.......#.#.#...#.#
###.#####.#.###.#.#####.#.###.#####.#.###.###.#.#####.#.#.###.#.#######.#.#.#.#.#
#.#.#.....#.#a..#.#...#.#.#...#.....#...#...#i#.#...#...#.Y.#.#.#....w..#.#.#...#
#.#R#######.#.#.#.###.#.#.#.###.#######.###.#.#.#.#.#######.#.#.#####.#.#.#.#####
#...........#.#.......#.....#...........#.....#x..#.........#.........#.#.......#
#################################################################################";
    
    
    public static string INPUT2 = @"#################################################################################
#.......#.A...........#.........#.......#.#.........#.............#...#..r......#
#.###.###.#####.#####.#.#######.#.#######.#.#.#####.#.#.#.#######.###.#.###.###.#
#...#.#...#.....#.#...#...#.....#.......#...#.#...#o#.#.#.#...#.#...#.#...#.#...#
#####.#.###.#####.#.###.#W###.#########.#####.#.#.###.#.#.#.#.#.###.#K###.#.#####
#.....#.#.#...#...#...#.#...#...........#...#...#.....#.#.#.#.#.#...#...#.#.....#
#M###.#.#.###.#.#####.#####.###########.#.#.###.#######.###.#.#.#.#####.#.#####.#
#.#...#...#...#.#...#.....#...#..z....#.#.#...#...#.....#...#.#.#.#...#.......#.#
#.###.###.#.###.#.#.#####.###.#.###.#.#.#.###.#####.#.###.###.#.#.#.#.#####.###.#
#...#...#.#.#....y#.....#.....#.#.#.#.#.#...#.#...#.#.#...#...#.#...#.#...#.#m..#
#.#.#####.#.###########.#######.#.#.#.#.###.#.#.#X#.#.#.###.###.#####.#.#.###.###
#.#.#...#.#s..#.......#.......#...#.#.#.#...#...#.#.#.#.#.#.#.......#...#...#...#
###.#.#.#.###.#.#####.###.###.#####.#.#.#.#######.#.###.#.#.#.#####.#######.###.#
#...#.#...#.#...#...#.#...#.......#.#.#.#.#.......#.....#.#.#.#.....#.....#.....#
#.###.#####.#####.#.#C#.###.#####.#.#.#.#.#####.###.#####.#.###.#####.#.#.#####.#
#.....#.....#.....#.#.#.#...#...#...#.#.#.#.F.#...#...#...#...#.#...#.#.#.....#.#
#.#######.#.###.###.#.#.#####.#.#######.#.#.#.###.###.###.###.#.#.#.#.#.#######.#
#.#.......#...#.#...#.#...#...#.#.......#...#.#.#...#.......#.#.#.#.#.#.........#
#.#.#########.#.#####.###N#.###.#.###########.#.###.#########.#.#.#.#.###########
#...#...#.......#.....#...#.#.#.#.......#...#.#...............#...#.#.#....q....#
#####.###.#######.#####.###.#.#.#######.#.#.#.#############.#####.#.#.#.#.#####.#
#g..#.....#.....#...#.#...#...#.......#.#.#.#..l..........#.#...#.#.#.#.#...#...#
###.#.#####.###.###.#T#.#.###.###.#####.###.#############.#####B#.#.#.#.###.#####
#...#.#...#...#.....#.#.#...#.#.#.#...#.#.......#.......#...#...#.#...#...#.....#
#.###.###.###.#####.#.###.###.#.#.#.#.#.#.#####.#.###.#####.#.###.#####.#######.#
#...#...#...#.#.#...#...#.I...#.#...#...#.....#.#...#.#...#...#.#...#.#.#.......#
###.###.#.###.#.#.#####.#####.#.#############.#####.#.#.#.#####.###.#.#.#.#######
#.....#.#...#.#.......#.#...#...........#.....#.....#...#.......#.#.#.#.#.......#
#.#####.###.#.#######.#.#.#.#####.#######.###.#.###########.###.#.#.#.#.#######.#
#...........#.#e....#.#...#...#...#.....#.#...#...#.........#.....#.#...#.......#
#.###########.#.###.#########.#####.###.#.#######.#.#####.#######.#.#####.#####.#
#.....#.#.....#.#.#.........#.......#...#.#.......#.#.....#.....#.#...#...#.#...#
#####.#.#.#####.#.#####.#.###########.###.#.#######.#####.#.###.#.###.#.###.#.###
#...#.#.#.......#.#.....#.#.........#.#.#...#.#.....#...#.#.#...#...#.#...#...#.#
#.###.#.#########.#.#####.#V#.#####.#.#.#.###.#.###.#.#.###.#.#######.###.#.###.#
#.#...#.....#.....#.#.....#.#...#...#.#.#.#...#.#.#.#.#.....#.........#...#.#...#
#.#.###.###.#.#####.#######.###.#.###.#.#.###.#.#.#.#.#################.###.#.#.#
#.#.....#.#.#.....#.......#.#.#.#...#.#.#.#...#.#...#.#.........#.......#.S.#.#.#
#.#######.#.#####.#######.#.#.#.#####.#.#.#.#.#.#####.#####.###.#.#######.###.#.#
#.......................#.....#........@#@..#.#.............#.....#...........#.#
#################################################################################
#...............#.....#.....#..........@#@#.........................D.......#..u#
#.#############.#####.#.#.###.###.#####.#.#.#.#####.#######.###############.#.###
#.....#.....#...#...#...#.....#.#.#.....#...#....v#.#.....#.#.......#.....#.#.E.#
#####.#.#####.###.#.#.#########.#.#######.#######.###.###.###.#####.#.#####.#.#.#
#.....#.....#.....#.#.#...#.....#.......#.#.......#.....#.#...#...#.#....j#t#.#.#
#.#########.#######.#.#.#.#.###########.#.#.#######.#####.#.###.###.#####.#.#.#.#
#.......#...#...#...#...#...#.......#...#.#.#.....#.#.....#.#.....#.#...#.#.#.#.#
#######.#.#.###.#.#######.###.#####.#.#####.#.###.#.#.#####.#####.#.#.#.#.#.###.#
#.....#.#.#.....#...#.....#...#.....#...#...#.#.#...#.....#.......#...#.#.#.#...#
###.###.#.#####.###.#####.#.###.#####.#.#.#.#.#.#########.#######.#####.#.#.#.#.#
#...#...#...#...#.#.....#.#.#.#.#.....#.#.#d#.#.....#.......#.....#.....#.#...#.#
#.###.#####.#.###.#####.#.#.#.#.#######.#.###.###.#.#.#######.#####.#####.#####.#
#.....#...#.#.....#.....#.#.#.#...#.....#.....#...#.#.....#.....#...#...#.....#.#
#.#####.#.#.#.#####.#####.#.#.###.#.###.#######.#.#######.#.#####.#####.#.#.#.#.#
#.#.....#.#.#.#.....#.....#.#...#.#.#...#.......#.#.....#...#.#...#.....#.#.#.#.#
#.###.#.#.#.#.#.###########.###.#.#.#.###.#########.#.#######.#.#####.###.#.###.#
#.H.#.#.#.#.#.#.....#.....#.#...#...#...#.#.....#...#.........#.#.....#...#.....#
###.###.#.#.#.#####.#.###.#.#.#########.#.#.###.#.#######.#####.#.#.#.#.#########
#.#.#...#...#...#.#...#...#.#...#.......#...#.#...#.....#...#...#.#.#.#.........#
#.#.#.#.#######.#.#####.###.#.#.#.#######.###.#########.###.#.#####.#.#########.#
#...#.#.#...#.#.#...#...#...#.#.#...#...#...#...#.....#...#.#.#.....#.#.......#.#
#.###.###.#.#.#.###.#######.#.#.###.#.#.###.#.###.#.#.#.#.#.###.#####.###.###.#.#
#.#...#...#.#.#.#...........#.#...#.#.#.#.#.#.#...#.#...#.#.....#...#...#.#.#.#.#
#.###.#.###.#.#.#.###########.###.#.#.#.#.#.#.#.###.#####.#####.###.###.#.#.#.#.#
#...#...#.#.#.#...#...#.U...#.#.#...#.#.#...#.....#.#.....#...#...#...#...#...#.#
###.#.###.#.#.#####J#.#.#.###.#.#####.###.#######.#.#####.#.#####.#.#####.#####.#
#...#.Q.#.#.#.....#.#...#.....#.........#.......#.#f....#.L.#.....#h....#.#...#.#
#.#####.#.#.###.#.#.#################.#.#######.#.#####.###.#.#####.#.###.#.#.#.#
#.#...#...#...#.#.#.#...#.......#...#.#.#.#...G.#.....#.Z.#.#...#...#.....#.#...#
#.#.#####.###.###.#.#.#.#####.#.#.#.###.#.#.#############.#.###.#########.#.#####
#k#.#.....#.#...#.#..c#...#...#...#.#...#.#.#........n#...#...#.#.......#.#...#.#
#.#.#.#####.###.#.#######.#.#######.#.#.#.#.#.#######.#.###.###.#.#####.#####.#.#
#.#...#.....#...#.#.P...#.#.#.....#...#.#.#.#.#...#...#.#...#...#.....#.....#p..#
#.###.#.#.###.###.#.#.###.#.###.#.#####.#.#.#.#.###.###.###.#.#######.###.#####.#
#...#...#.#...#.#...#...#.#...#.#...#...#.O.#.#.....#.#...#b#.#.......#.#.#...#.#
###.#####.#.###.#.#####.#.###.#####.#.###.###.#.#####.#.#.###.#.#######.#.#.#.#.#
#.#.#.....#.#a..#.#...#.#.#...#.....#...#...#i#.#...#...#.Y.#.#.#....w..#.#.#...#
#.#R#######.#.#.#.###.#.#.#.###.#######.###.#.#.#.#.#######.#.#.#####.#.#.#.#####
#...........#.#.......#.....#...........#.....#x..#.........#.........#.#.......#
#################################################################################";
}
​

é é é #test

Last Run:	12:57:40 am
Compile:	0.158s
Execute:	0.016s
Memory:	0b
CPU:	0.016s

View IL Code