/*
?*?程序參考：https://max.book118.com/html/2015/0619/19399060.shtm?數據結構課程設計報告--馬兒覆蓋問題.doc
?*?
?*/

using?System;
using?System.Collections.Generic;
using?System.Linq;
using?System.Threading;

class?Program
{
	/*以下變量為全局信息，各個函數可以調用*/
	static?private?int?M;//棋盤長
	static?private?int?N;//棋盤寬
	static?List?directionList;//方向列表，存儲馬可走的8個方向
	static?Dictionary?chessboard;//棋盤狀態，Postion代表棋盤位置，int代表是否有子。如果為0，表示未占用，為1表示占用。M*N個元素可以代表整個棋盤信息
	static?Postion?startPostion;//遍歷的起始點
	static?List?horseHome;//存儲運算結果馬所在的位置列表

	//獲得周圍可行格子坐標（最多8個）
	static?List?getValiablePos（Postion?postion）
	{
		List?valiablelist=new?List（）;

		//向周圍8個方向遍歷，如果新探索位置（newPostion）在棋盤外，則不予記錄，否則放到可行列表中
		foreach（var?i?in?directionList）
		{
			Postion?newPostion?=?new?Postion（postion?+?i）;

			if?（chessboard.ContainsKey（newPostion））
				valiablelist.Add（newPostion）;
		}
		return?valiablelist;
	}

	//獲得周圍八個格子中馬的數量
	static?int?getValiableNum（Postion?postion）
	{
		int?num?=?0;
		foreach（var?i?in?directionList）
		{
			Postion?tempPostion?=?new?Postion（postion?+?i）;
			//tempPostion在棋盤上且此位置有馬，則記錄
			if（chessboard.ContainsKey（tempPostion））
			{
				if?（chessboard[tempPostion]?==1）
					num++;
			}
		}
		return?num;
	}

	//核心算法
	static?void?find（Postion?myPostion）
	{
		List?ableList?=?getValiablePos（myPostion）;

		//條件一：拿掉當前位置的馬后，周圍馬的周圍必須至少有一個馬
		foreach（var?i?in?ableList）
		{
			if?（getValiableNum（i）?-?1?<=?0）
				return;
		}

		//條件二：拿掉當前位置的馬后，自己位置周圍至少有一個馬
		if?（getValiableNum（myPostion）?>?0）
		{
			chessboard[myPostion]?=?0;//滿足兩個條件后，可以拿掉當前位置的馬
			horseHome.Remove（myPostion）;
			draw（）;
		}
	}

	//通過chessboard畫棋盤
	static?void?draw（）
	{
		Console.Clear（）;
		int?number=0;
		String?str?=?““;
		foreach（var?i?in?chessboard）
		{
			str?+=?i.Value;
			str?+=?“?“;
			if（（number+1）%M==0）
			{
				str?+=?“\n“;
			}
			number++;
		}
		Console.WriteLine（str）;
		Thread.Sleep（200）;//可以看到執行過程
	}

	static?void?Main（string[]?args）
	{
		init（）;
		//對棋盤上的每一個位置用find（）來決定是否將當前位置的馬拿下去。
		List?newBoard?=?new?List（chessboard.Keys）;//chessboard運行中會變動，不能用于枚舉，要用newBoard作中間變量
		foreach?（v