#include<iostream>
using namespace std;
/*
解布線問題：
布線問題的解空間是一個圖。
從位置a開始將它作為第一個擴展結點。與該擴展結點相鄰并且可達的方格成為可行結點被加入到
活結點隊列中，并且將這些方格標記為1。接著，從活結點隊列中取出隊首結點作為下一個擴展結點，并將與
當前擴展結點相鄰且未標記過的方格標記為2，并存入活結點隊列。這個過程一直繼續到算法搜索到目標方格b
或活結點隊列為空時為止。
*/

class Position
{
public:
	Position()
	{
	}
	Position* operator=(const Position& a)
	{
		row = a.row;
		col = a.col;
		movedirection = a.movedirection;
		return this;
	}
public:
		int row;
		int col;
		int movedirection;
};

/*
用一個二維數組grid表示所給的方格陣列。初始時，grid[i][j]=0,表示該方格允許布線
，grid[i][j]=1表示方格被封鎖，不允許布線。為了便于處理方格邊界的情況，算法在所給方格
陣列四周設置一道“圍墻”，即增設標記為“1”的附加方格。算法開始時測試初始方格與目標
方格是否相同。如果這兩個方格相同則不必計算，直接返回最短距離0，否則算法設置方格陣列的
“圍墻”，初始化位移矩陣offset,
*/
template<class Type>
class Queue
{
	public:
		Type *H;
		int Capacity;
		int Size;
		int Front;
		int Rear;
	public:
		Queue(int n)
		{
			H = NULL;
			H = new Type[n+1];
			Capacity = n;
			Size = 0;
			Front = 0;
			Rear = 0;
		};
		Queue( Queue& a )
		{
			//要排除自賦值的情況
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				this.Front = a.Front;
				this.Rear = a.Rear;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[i];
				}
			}
		};

		void Add( Type& node )
		{
			if ( Size == Capacity )
			{
				cout<<"capacity"<<endl;
				return;
			}
			else
			{
				if ( Rear + 1 == Capacity )
				{
					H[Rear] = node;
					Rear = 0;
					++Size;
				}
				else
				{
					H[Rear] = node;
					++Size;
					++Rear;
				}
			}
			
		};

		void Delete( Type& node )
		{
			if ( Size == 0 )
			{
				return;
			}
			else
			{	
				if ( Front == Capacity )
				{
					Front = 0;
				}
				node = H[Front];
				++Front;
				--Size;
			}
		};

		bool IsEmpty()
		{
			return ( 0 == Size );
		};
};

int m = 5;
int n = 6;
int grid[7][8] = { 0 };
bool FindPath( Position start,Position finish,int& PathLen,Position* &path )
{
	//計算從起始位置start到目標位置finish的最短布線路徑
	//找到最短布線路徑則返回true,否則返回false
	if ( ( start.row == finish.row ) 
		 && ( start.col == finish.col ) )
	{
		PathLen = 0;
		return true;
	}
	//否則首先設置方格陣列“圍墻”
	for ( int i = 0; i <= m + 1; ++i )
	{
		grid[0][i] = grid[n+1][i] = 1;
		//頂部和底部
	}
	for ( i = 0; i <= n + 1; ++i )
	{
		grid[i][0] = grid[i][m+1] = 1;
		//左和右
	}
	//初始化相對位移
	Position offset[4];
	offset[0].row = 0;
	offset[0].col = 1;
	//右初始化
	offset[1].row = 1;
	offset[1].col = 0;
	//下
	offset[2].row = 0;
	offset[2].col = -1;
	//左
	offset[3].row = -1;
	offset[3].col = 0;
	//上
	int NumOfNbrs = 4;
	//相鄰方格數
	Position here,nbr;
	here.row = start.row;
	here.col = start.col;
	grid[start.row][start.col] = 2;
	//標記可達方格的位置
	
	Queue< Position > Q(100);
	
	do
	{
		//標記可達相鄰方格
		for ( int i = 0; i < NumOfNbrs; ++i )
		{
			nbr.row = here.row + offset[i].row;
			nbr.col = here.col + offset[i].col;

			cout<<"nbr.row "<<nbr.row<<endl;
			cout<<"nbr.col "<<nbr.col<<endl;
			if ( grid[nbr.row][nbr.col] == 0 )
			{
				cout<<"增加新結點:"<<endl;
				//該方格未標記
				grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;
				if ( ( nbr.row == finish.row )
					&& ( nbr.col == finish.col ) ) 
				{
					break;
				}
				Q.Add( nbr );
				//可達接點作為向下遍歷的同層起點，圖的每一層
			}
		}
		
		//是否到達目標位置finish
		if ( ( nbr.row == finish.row )
			 && ( nbr.col == finish.col ) )
		{
			break;
			//完成布線
		}
		//活結點隊列是否非空
		if ( Q.IsEmpty() )
		{
			cout<<"start"<<endl;
			return false;
			//無解
		}
		Q.Delete( here );
		//取下一個擴展結點
	}while( true );
	//構造最短布線路徑
	PathLen = grid[finish.row][finish.col] - 2;
	path = new Position[PathLen];
	//從目標位置finish開始向起始位置回溯
	//肯定是一共經過PathLen個點，第一個點的標記為2，其后每層都
	//依次加1

	here = finish;
	for ( int j = PathLen - 1; j >= 0; --j )
	{
		path[j] = here;
		//找前驅位置

		for ( int i = 0; i < NumOfNbrs; ++i )
		{
			nbr.row = here.row + offset[i].row;
			nbr.col = here.col + offset[i].col;
			if ( grid[nbr.row][nbr.col] == j + 2 )
			//凡是有此標記的就是符合要求的點
			{
				cout<<"行是: "<<nbr.row<<" "<<"列是: "<<nbr.col<<endl;
				break;
			}
		}
		here = nbr;
		//向前移動
	}
	return true;
}

int main()
{
	Position start;
	start.row = 1;
	start.col = 1;
	Position finish;
	finish.row = 5;
	finish.col = 5;
	int PathLen;
	Position* path;
	FindPath( start, finish, PathLen, path );
	cout<<"第二次搜索: "<<endl;
	start.row = 2;
	start.col = 1;
	finish.row = 5;
	finish.col = 3;
	for( int i = 0; i < 7; ++i )
	{
		for( int j = 0; j < 8; ++j )
		{
			grid[i][j] = 0;
		}
	}
	
	FindPath( start, finish, PathLen, path );

	return 0;
}