深度优先搜索算法————卒子穿阵 一.实验内容：在一个 4*4 的阵列内，1 表示敌兵驻守区域，不能进入，0 区域可 以行走，编写程序实现卒子从（0，1）处进入从（3，3）处出来的路径。 二．实验代码： #include #define ROW 4 #define LINE 4 //行 //列 struct point { int row, line; } stack[100]; int top = 0; //栈顶位置 void push(struct point p) { stack[top++] = p; struct point pop() { return stack[--top]; //压栈 //弹栈 } } } }; //判断栈空 int empty() { return top == 0; int Maze[ROW][LINE] = { //迷宫阵列 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, void print() { //显示迷宫阵列 int i, j; for (i = 0; i < ROW; i++) { for (j = 0; j < LINE; j++) printf(" %d ", Maze[i][j]); printf("\n"); } printf("-------------\n"); 

} }; struct point before[ROW][LINE] = { {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}} void visit(int row, int line, struct point bef) { struct point visit_point = { row,line }; Maze[row][line] = 2; before[row][line] = bef; push(visit_point); //将该点入栈 } //各点的前驱，全部初始化为(-1,-1) //走到该点 //走过的点赋值为 2，防止重复走 int main() { struct point p = { 0, 1 }; //起点 Maze[p.row][p.line] = 2; push(p); //起点赋值为 2，避免重复走 //该点入栈 while (!empty()) { p = pop(); if (p.row == ROW - 1 && p.line == LINE - 1) break; if (p.line+1 < LINE && Maze[p.row][p.line+1] == 0) if (p.row+1 < ROW && Maze[p.row+1][p.line] == 0) visit(p.row, p.line+1, p); visit(p.row+1, p.line, p); if (p.line-1 >= 0 && Maze[p.row][p.line-1] == 0) if (p.row-1 >= 0 && Maze[p.row-1][p.line] == 0) visit(p.row, p.line-1, p); visit(p.row-1, p.line, p); //往右边走 //往下边走 //往左边走 //往上边走 print(); //显示当前状态的迷宫阵列 } if (p.row == ROW - 1 && p.line == LINE - 1) { printf("最优深度搜索路径为:\n"); printf("(%d , %d)\n", p.row, p.line); while (before[p.row][p.line].row != -1) 

{ } p = before[p.row][p.line]; printf("(%d , %d)\n", p.row, p.line); //输出路径 } else printf("没有路径!\n"); return 0; } 四．实验结果：