迷宫问题.cpp

迷宫问题

#include <iostream> 
#include <fstream>  //文件输入/输出(文件流)
#include <cstring> 
using namespace std;
class TStatus 
{
public: 
int step,i,j,d; 
TStatus *next; 
void assign(int step=0, int i=0, int j=0, int d=0, TStatus *next=NULL) 
{
	this->step=step;this->i=i;this->j=j;this->d=d;this->next=next;
} 
TStatus(int step=0,int i=0,int j=0,int d=0,TStatus *next=NULL) 
{
	assign(step,i,j,d,next); 
} 
}; 
class TPath 
{ 
private: 
TStatus *path; 
int path_len,max_len; 
public: 
TPath(int max_len) 
{ 
if (max_len<0) max_len=0; 
this->max_len=max_len; 
path=NULL; 
path_len=0; 
path=new TStatus[max_len]; 
if (!path) this->max_len=0;else memset(path,0,max_len*sizeof(TStatus)); 
} 
~TPath() {if (path) delete[] path;} 
bool set_last_step(int step, const TStatus &s) 
{ 
if (!path || step < 0 || step >= max_len) { return false; } 
path[step] = s; path_len = step + 1; 
return true; 
} 
void print(ostream &os) const 
{ 
for (int i = 0; i < path_len; i++) { if (i != 0) os << ','; os << '(' << path[i].i + 1 << ',' << path[i].j + 1 << ',' << path[i].d + 1 << ')'; } 
os << endl; 
} 
}; 
class TStack 
{ 
private: 
TStatus *top; 
public: 
TStack() { top = NULL; } 
~TStack() { TStatus s; while (!empty()) pop(s);} 
bool empty() const { return top == NULL; } 
bool push(const TStatus &s) 
{ 
TStatus *new_node = new TStatus(s.step, s.i, s.j, s.d, top); 
if (!new_node) return false; 
top=new_node; 
return true; 
} 
bool pop(TStatus &s) 
{ 
if (empty()) 
return false; 
TStatus *tmp = top; 
top = top->next; 
tmp->next = NULL; 
s = *tmp; 
delete tmp; 
return true; 
} 
}; 
class TMaze 
{ 
private: 
int **maze; 
int m,n; 
public: 
~TMaze() 
{ 
if (maze) 
{ 
for (int i = 0; i < m; i++) delete[] maze[i]; 
delete[] maze; 
} 
} 
void restore() 
{ 
for (int i = 0; i < m; i++) 
for (int j = 0; j < n; j++) 
if (maze[i][j] == -1) maze[i][j] = 0; 
} 
TPath *find_path(int start_i, int start_j, int end_i, int end_j) 
{ 
const int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; 
TPath *path = NULL; 
start_i--; start_j--; end_i--; end_j--; 
if (start_i < 0 || start_i >= m) return NULL; 
if (start_j < 0 || start_j >= n) return NULL; 
if (end_i < 0 || end_i >= m) return NULL; 
if (end_j < 0 || end_j >= n) return NULL; 
if (maze[start_i][start_j] != 0 || maze[end_i][end_j] != 0) return NULL; 
path = new TPath(m*n); 
if (!path) return NULL; 
if (start_i == end_i && start_j == end_j) return path; 
TStatus cur(0, start_i, start_j, -1); 
TStack stack; 
stack.push(cur); 
maze[start_i][start_j] = -1; 
while (!stack.empty()) 
{ 
stack.pop(cur); 
cur.d++; 
while (cur.d<4) 
{ 
int new_i=cur.i+dir[cur.d][0]; 
int new_j=cur.j+dir[cur.d][1]; 
if (new_i>=0 && new_i<m && new_j>=0 && new_j<n && maze[new_i][new_j]==0) 
{ 
if (new_i == end_i && new_j == end_j) 
{ 
path->set_last_step(cur.step, cur); 
restore(); 
return path; 
} 
stack.push(cur); 
path->set_last_step(cur.step, cur); 
cur.assign(cur.step+1,new_i,new_j,-1); 
stack.push(cur); 
maze[new_i][new_j]=-1; 
break; 
} 
cur.d++; 
} 
} 
delete path; 
restore(); 
return NULL; 
} 
TMaze(char *filename) 
{ 
int i,j; 
m=0; 
n=0; 
maze=NULL; 
ifstream file(filename); //默认打开方式:文本方式
file>>m>>n; 
if (m<=0 || n<=0) { m = 0; n = 0; return; } 
maze = new int *[m]; 
if (!maze) { m = 0; n = 0; return; } 
for (i = 0; i < m; i++) 
{ 
maze[i] = new int[n]; 
if (!maze[i]) 
{ 
for (j = 0; j < i; j++) 
delete[] maze[j]; 
delete[] maze; 
maze = NULL; 
m = 0; 
n = 0; 
return; 
} 
else 
memset(maze[i], 0, sizeof(int)*n); 
} 
for (i=0;i<m;i++) 
for (j=0;j<n;j++) 
file>>maze[i][j]; 
} 
}; 
int main() 
{ 
TMaze maze("迷宫模型.txt"); 
int start_i = 0, start_j = 0, end_i = 0, end_j = 0; 
cout<<"				 迷宫问题";
cout<<endl<<"请输入起始坐标和终点坐标(y1 x1 y2 x2):"; 
cin>>start_i>>start_j>>end_i>>end_j; 
TPath *path; 
path = maze.find_path(start_i, start_j, end_i, end_j); 
if (path) 
{ 
	cout<<"通路为(x,y,z(方向:(1右 2下 3左 4上)):"<<endl;
	path->print(cout); delete path; 
} 
else cout<<"没有通路!"<<endl; 
return 0; 
}