/* 
Matrix:矩陣類 
offsets:搜索偏移 
enum directions:四個方向 
struct item:搜索節點 
Migong:迷宮類 
1.創建一個Migong對象 
2.使用用Create方法輸入數據 
3.使用Solve方法進行求解 
4.ShowSolve方法顯示解 
5.可以重復使用Create方法 
6.入口只能在左上角 
7.默認出口在右下角 
ShowAllPath:窮舉所有的路徑 
備注: 
由于算法原因,這里的所有路徑應該是指介于: 
a.如果兩條路存在某個點不同那么就是不同的路 
b.如果在一條路中去掉一個或者一個以上的圈,那么他們是同一條路之間意義上的路 
*/ 

#include <iostream> 
#include <stack> 
#include <vector> 

using namespace std; 

#ifndef MIGONG_H 
#define MIGONG_H 
 
//////////////////////////矩陣類////// /////////////////// 

class Matrix
{ 
	int* m; 
	int row, col; 
	bool iscreate; 
	
public: 
	Matrix(){m=0;iscreate=false;}; //構造函數
	~Matrix() {Release();}; //析構函數
	bool Create(int, int); 
	int& operator () (int, int); 
	int GetRow(){return row;}; 
	int GetCol(){return col;}; 
	void Release(); 
	void Show(char, char ); 
}; 


bool Matrix::Create(int r, int c) 
{ 
	if( r<=0 || c<=0) return false; 
	
	Release(); 
	
	row = r; 
	col = c; 
	m = new int[row*col]; 
	
	for (int i=0;i<row*col;i++) 
	{ 
		*(m+i) = 0; 
	} 
	iscreate = true; 
	return true; 
} 


int& Matrix::operator ()(int r, int c) 
{ 
return *(m+r*col+c); 
} 


void Matrix::Release() 
{ 
	if (iscreate) 
	{ 
		row = col = 0; 
		if (m) delete[] m; 
		m = 0; 
	} 
	iscreate = false; 
} 


void Matrix::Show(char blk='#', char nblk=' ') 
{ 
	int i, j; 
	for (i=0;i<row;i++) 
	{ 
		for (j=0;j<col;j++) 
		{ 
			if (*(m+i*col+j) == 0) 
				cout<<nblk; 
			else 
				cout<<blk; 
		} 
		cout<<endl; 
	} 
} 
///////////////////////////// 
////迷宮相關數據結構的定義/// 
///////////////////////////// 
struct offsets		//搜索偏移
{ 
	int a, b; 
}; 

enum directions		//按順時針方向來找
{ 
	_S = 0, 
	_E, 
	_N, 
	_W 
}; 

struct item			//搜索節點
{ 
int row, col, dir; 
}; 

class Migong
{ 
	static offsets move[4];
	Matrix maze; 
	Matrix mark; 
	int row; 
	int col; 
	int desr; 
	int desc; 
	stack<item> stk; 
	bool iscreate; 
	int pathlength; 
	bool GetPath(); 
	bool IsInPath(int, int); 
public: 
	Migong(){issolved=false;result=0;pathlength=row=col=0;iscreate=false;}; 
	~Migong(){Release();}; 
	bool Create(int* , int , int , int , int ); 
	void Solve(); 
	void Release(); 
	void OutputMaze(); 
	void ShowSolve(char, char ); 
public: 
	bool issolved; 
	item* result; 
}; 

offsets Migong::move[4]={ {1, 0}, {0, 1}, 
{-1, 0}, {0, -1}}; 

//////////////////////////// 
//迷宮數據應該是不含邊框的// 
//////////////////////////// 
bool Migong::Create(int* m, int r, int c, int desrow=-1, int descol=-1) 
{ 
if (r<=0 || c<=0) return false; 

Release(); 

if (desrow==-1 || descol==-1) 
{ 
desr = r; 
desc = c; 
} 
else 
{ 
desr = desrow; 
desc = descol; 
} 

row = r; 
col = c; 
maze.Create(r+2, c+2); 
mark.Create(r+2, c+2); 

int i, j; 

for (i=0;i<r+2;i++) 
{ 
for (j=0;j<c+2;j++) 
{ 
if (j==0 || j==c+1 || i==0 || i==r+1) 
{ 
mark(i, j) = maze(i, j) = 1; 

}else 
{ 
mark(i, j) = 0; 
maze(i, j) = m[((i-1)*col+j-1)]; 
} 
} 
} 
return iscreate = true; 
} 

bool Migong::GetPath() 
{ 
mark(1,1) = 1; 
item temp; 
temp.col = 1; 
temp.row = 1; 
temp.dir = _S; 
stk.push(temp); 

while (!stk.empty()) 
{ 
temp = stk.top(); 
stk.pop(); 

int i = temp.row; 
int j = temp.col; 
int d = temp.dir; 

while (d<4) 
{//根據當前點的狀態確定下一個搜索點 
int g = i + move[d].a; 
int h = j + move[d].b; 

if (g==desr && h==desc) 
{ 
return true; 
} 
//如果這個點不是障礙點且沒有被搜索過那么可以對這個點進行搜索 
if (maze(g, h)==0 && mark(g, h)==0) 
{ 
mark(g, h) = 1; 
temp.row = g; 
temp.col = h; 
temp.dir = d+1; 
stk.push(temp); 
i = g; 
j = h; 
d = _S;//對一下個點進行搜索 
} 
else d++; 
} 
} 
return false; 
} 

void Migong::Solve() 
{ 
issolved = GetPath(); 
if (issolved) 
{ 
pathlength = stk.size(); 
result = new item[pathlength]; 
for (int i=0;i<pathlength;i++) 
{ 
*(result+i) = stk.top(); 
stk.pop(); 
// cout<<"("<<(*(result+i)).row<<","<<(*(result+i)).col<<")"<<endl; 
} 
} 
while (!stk.empty()) 
stk.pop(); 
} 

void Migong::Release() 
{ 
if (iscreate) 
{ 
maze.Release(); 
mark.Release(); 
row=col=0; 
if (result) 
delete [] result; 
result = 0; 
while (!stk.empty()) 
stk.pop(); 
} 
iscreate = false; 
issolved = false; 
pathlength = 0; 
} 

void Migong::OutputMaze() 
{ 
if (!iscreate) return; 
maze.Show(); 
} 

bool Migong::IsInPath(int r, int c) 
{ 
if (!iscreate || !issolved) 
return false; 

item temp; 
for (int i=0;i<pathlength;i++) 
{ 
temp = *(result+i); 
if ((temp.row==r) && (temp.col==c)) 
return true; 
} 

return false; 
} 

void Migong::ShowSolve(char blk='#',char s='o') 
{ 
if (!iscreate) return; 
if (!issolved) 
{ 
cout<<"無解"<<endl; 
} 
else 
{ 
int i, j; 
for (i=0;i<row+2;i++) 
{ 
for (j=0;j<col+2;j++) 
{ 
if ((i==1 && j==1) || (i==desr && j==desc)) 
{ 
cout<<s; 
} 
else if (maze(i, j) == 1) 
{ 
cout<<blk; 
}else 
{ 
if (IsInPath(i, j)) 
cout<<s; 
else 
cout<<' '; 
} 
} 
cout<<endl; 
} 
} 
} 

////////////////////// 
//////窮舉所有路徑//// 
////////////////////// 
offsets move[4]={ {1, 0}, {0, 1}, 
{-1, 0}, {0, -1}}; 

struct node 
{ 
int row,col; 
}; 

vector<node> path; 
int count; 
bool IsReachable( Matrix& maze, Matrix& mark, node beg, node des) 
{ 
if (beg.row==des.row&&beg.col==des.col) 
{//如果達到的話那么顯示路徑 
count++; 
cout<<"第"<<count<<"條路徑:"<<endl; 
for (int i=0;i<path.size();i++) 
cout<<"("<<path[i].row<<","<<path[i].col<<")"; 
cout<<"("<<des.row<<","<<des.col<<")"; 
cout<<endl; 
return false; 
} 
if (maze(beg.row, beg.col)==1 || mark(beg.row, beg.col)==1) 
{ 
return false; 
} 

path.push_back(beg); 
mark(beg.row, beg.col) = 1; 

node nextnode; 

for (int i=_S;i<_W+1;i++) 
{ 
nextnode.row = beg.row + move[i].a; 
nextnode.col = beg.col + move[i].b; 

IsReachable(maze, mark, nextnode, des); 
} 

path.resize(path.size()-1); 
mark(beg.row, beg.col) = 0; 

return false;//如果不是窮舉的話應該根據for循環的結果重新設置返回值 
} 

/* 
參數maze,mark為迷宮長寬均加二的矩陣 
desr,desc為出口點 
*/ 
void FindAllPath( Matrix& maze, Matrix& mark, int desr, int desc) 
{ 
node first, last; 
first.row = 1; 
first.col = 1; 
last.row = desr; 
last.col = desc; 

IsReachable(maze, mark, first, last); 

path.clear(); 
} 

/* 
m迷宮矩陣數據 
r,c行和列的大小 
desr,desc目標位置 
*/ 
void ShowAllPath(int* m, int r, int c, int desr=-1, int desc=-1) 
{ 
Matrix maze, mark; 
maze.Create(r+2, c+2); 
mark.Create(r+2, c+2); 

if (desr==-1 || desc==-1) 
{ 
desr = r; 
desc = c; 
} 

int i, j; 

for (i=0;i<r+2;i++) 
{ 
for (j=0;j<c+2;j++) 
{ 
if (j==0 || j==c+1 || i==0 || i==r+1) 
{ 
mark(i, j) = maze(i, j) = 1; 

}else{ 
mark(i, j) = 0; 
maze(i, j) = m[((i-1)*c+j-1)]; 
} 
} 
} 

count = 0; 
FindAllPath(maze, mark, desr, desc); 

maze.Release(); 
mark.Release(); 
} 
#endif

int main()
{
	return 0;
}