+Ȧ

几个开发用的小程序,很容易懂的,非常实用,大家可以

问题描述: 
以一个m*n 的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口的通道，或得出没有通路的结论。 

内容： 
首先实现一个以链表作存储结构的栈类型，然后编写一求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通道为：(1,1,),(1,2,2),(2,2,2),(3,2,3),(3,1,2),…… 
迷宫数据从文件中读取出来
问题补充：问题描述里漏了几个字：……求出一条从入口到出口的通道…… 

测试数据如下:左上角(1,1)为入口，右下角(8,9)为出口 
0 0 1 0 0 0 1 0 
0 0 1 0 0 0 1 0 
0 0 0 0 1 1 0 1 
0 1 1 1 0 0 1 0 
0 0 0 1 0 0 0 0 
0 1 0 0 0 1 0 1 
0 1 1 1 1 0 0 1 
1 1 0 0 0 1 0 1 
1 1 0 0 0 0 0 0
提问者： 刺客※※ - 魔法学徒 一级 
最佳答案
纠正一下，终点应该为(9,8),而不是(8,9)，否则与示例通道的坐标表示不符。 

迷宫输入文件input.txt: 
9 8 
0 0 1 0 0 0 1 0 
0 0 1 0 0 0 1 0 
0 0 0 0 1 1 0 1 
0 1 1 1 0 0 1 0 
0 0 0 1 0 0 0 0 
0 1 0 0 0 1 0 1 
0 1 1 1 1 0 0 1 
1 1 0 0 0 1 0 1 
1 1 0 0 0 0 0 0 

运行示例： 
input start_i start_j end_i end_j: 1 1 9 8 
(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),(4,1,2),(5,1,1),(5,2,1),(5,3,2),(6,3,1),(6,4,1),(6,5,4),(5,5,1),(5,6,1),(5,7,2),(6,7,2),(7,7,2),(8,7,2),(9,7,1) 

源码如下： 
#include <iostream> 
#include <fstream> 
#include <string.h> 
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("input.txt"); 
int start_i = 0, start_j = 0, end_i = 0, end_j = 0; 
cout << "input start_i start_j end_i end_j: "; 
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) { path->print(cout); delete path; } 
else cout << "No path!" << endl; 
return 0; 
}