using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;


public class DukeOnChessBoard
{
	bool[][] visited;
	int n;
	public string dukePath(int m, string initPosition)
	{
		n = m;
		visited = new bool[n][];
		for (int i = 0; i < n; i++)
		{
			visited[i] = new bool[n];
		}

		string t = dfs(initPosition, "").Trim('-');
		if (t.Length >= 40)
		{
			t = t.Substring(0, 20).Trim('-') + "..." + t.Substring(t.Length-20).Trim('-');
		}
		return t;
	}

	string soFar = "";
	private string dfs(string cur, string path)
	{
		int x, y;
		x = cur[0] - 'a';
		y = cur[1] - '1';

		if (x >=n || y >= n || x < 0 || y < 0 || visited[x][y])
			return path;

		visited[x][y] = true;
		path += cur + "-";

		if (
			(x + 1 < n && visited[x + 1][y]) ||
			(y + 1 < n && visited[x][y + 1]) ||
			(y - 1 >= 0 && visited[x][y - 1]) ||
			(x - 1 >= 0 && visited[x - 1][y]))
		{
			if (path.Length > soFar.Length)
			{
				return path;
			}
			else if (path.Length == soFar.Length)
			{
				return String.Compare(path, soFar) > 0 ? path : soFar;
			}
			else
			{
				return soFar;
			}
		}


		string[] arr = new string[4];
		arr[0] = dfs(String.Format("{0}{1}", (char)('a' + x + 1), (char)(y+'1')), path);
		arr[1] = dfs(String.Format("{0}{1}", (char)('a' + x), (char)(y + 1 + '1')), path);
		arr[2] = dfs(String.Format("{0}{1}", (char)('a' + x), (char)(y - 1 + '1')), path);
		arr[3] = dfs(String.Format("{0}{1}", (char)('a' + x - 1), (char)(y + '1')), path);
		Array.Sort(arr);

		return arr[3];
	}

	// BEGIN KAWIGIEDIT TESTING
	// Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
	#region Testing code generated by KawigiEdit
	[STAThread]
	private static Boolean KawigiEdit_RunTest(int testNum, int p0, string p1, Boolean hasAnswer, string p2) {
		Console.Write("Test " + testNum + ": [" + p0 + "," + "\"" + p1 + "\"");
		Console.WriteLine("]");
		DukeOnChessBoard obj;
		string answer;
		obj = new DukeOnChessBoard();
		DateTime startTime = DateTime.Now;
		answer = obj.dukePath(p0, p1);
		DateTime endTime = DateTime.Now;
		Boolean res;
		res = true;
		Console.WriteLine("Time: " + (endTime - startTime).TotalSeconds + " seconds");
		if (hasAnswer) {
			Console.WriteLine("Desired answer:");
			Console.WriteLine("\t" + "\"" + p2 + "\"");
		}
		Console.WriteLine("Your answer:");
		Console.WriteLine("\t" + "\"" + answer + "\"");
		if (hasAnswer) {
			res = answer == p2;
		}
		if (!res) {
			Console.WriteLine("DOESN'T MATCH!!!!");
		} else if ((endTime - startTime).TotalSeconds >= 2) {
			Console.WriteLine("FAIL the timeout");
			res = false;
		} else if (hasAnswer) {
			Console.WriteLine("Match :-)");
		} else {
			Console.WriteLine("OK, but is it right?");
		}
		Console.WriteLine("");
		return res;
	}
	public static void Main(string[] args) {
		Boolean all_right;
		all_right = true;
		
		int p0;
		string p1;
		string p2;
		
		// ----- test 0 -----
		p0 = 3;
		p1 = "b2";
		p2 = "b2-c2-c3-b3-a3-a2-a1-b1-c1";
		all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
		// ------------------
		
		// ----- test 1 -----
		p0 = 4;
		p1 = "d4";
		p2 = "d4-d3-d2-d1-c1-c2-c3...b3-b2-b1-a1-a2-a3-a4";
		all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
		// ------------------
		
		// ----- test 2 -----
		p0 = 3;
		p1 = "a2";
		p2 = "a2-b2-c2-c3-b3-a3";
		all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
		// ------------------
		
		// ----- test 3 -----
		p0 = 4;
		p1 = "d3";
		p2 = "d3-d4-c4-c3-c2-d2-d1...b2-b3-b4-a4-a3-a2-a1";
		all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
		// ------------------
		
		// ----- test 4 -----
		p0 = 8;
		p1 = "a8";
		p2 = "a8-b8-c8-d8-e8-f8-g8...a1-a2-a3-a4-a5-a6-a7";
		all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
		// ------------------
		
		// ----- test 5 -----
		p0 = 5;
		p1 = "a4";
		all_right = KawigiEdit_RunTest(5, p0, p1, false, p2) && all_right;
		// ------------------
		
		if (all_right) {
			Console.WriteLine("You're a stud (at least on the example cases)!");
		} else {
			Console.WriteLine("Some of the test cases had errors.");
		}
		Console.ReadKey();
	}
	#endregion
	// END KAWIGIEDIT TESTING
}
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!
