c语言迷宫问题，以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。

Question

以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。注意，程序必须是非递归的。
Input

第一行输入m和n，接下来是代表迷宫的0-1矩阵，最后一行是入口和出口的坐标。注意，坐标的起始编号是0。

Output

假如存在通路，则输出Yes,否则输出No。

Answer 1

#define STACK_SIZE 1000
#define TRUE 1
#define FALSE 0

#include <stdio.h>

short DIRECTION_UP = 1;
short DIRECTION_RIGHT = 1 << 1;
short DIRECTION_DOWN = 1 << 2;
short DIRECTION_LEFT = 1 << 3;
short ALL_DIRECTIONS = DIRECTION_UP | DIRECTION_RIGHT | DIRECTION_DOWN | DIRECTION_LEFT;

typedef struct {
  int x;
  int y;
  short directions;
} Cell;

typedef struct {
  Cell elem[STACK_SIZE];
  int top;
} Stack;

void initStack(Stack *s) {
  s->top = -1;
}

int isEmpty(Stack *s) {
  return (s->top == -1 ? TRUE : FALSE);
}

void push(Stack *s, Cell e) {
  s->top++;
  s->elem[s->top] = e;
}

void pop(Stack *s, Cell *e) {
  *e = s->elem[s->top];
  s->top--;
}

int hasDirection(Cell *e, short d) {
  return (e->directions & d) != 0 ? 1 : 0;
}

void removeDirection(Cell *e, short d) {
  e->directions = e->directions & (~d);
}

int main() {
  int i, j;
  int m, n;
  int entranceX, entranceY, exitX, exitY;
  scanf("%d %d", &m, &n);
  short a[m][n];
  short visited[m][n];
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      scanf("%d", &a[i][j]);

      visited[i][j] = 0;
    }
  }
  scanf("%d %d %d %d", &entranceX, &entranceY, &exitX, &exitY);

  Stack steps;
  initStack(&steps);
  Cell e;
  e.y = entranceX;
  e.x = entranceY;
  e.directions = ALL_DIRECTIONS;

  push(&steps, e);
  visited[entranceX][entranceY] = 1;
  while (!isEmpty(&steps)) {
    pop(&steps, &e);
    if (e.x == exitX && e.y == exitY) {
      push(&steps, e);
      break;
    }

    if (e.x > 0 && hasDirection(&e, DIRECTION_UP) && a[e.x - 1][e.y] == 0 && !visited[e.x - 1][e.y]) {
      removeDirection(&e, DIRECTION_UP);
      push(&steps, e);
      e.x--;
      e.directions = ALL_DIRECTIONS;
      removeDirection(&e, DIRECTION_DOWN);
      push(&steps, e);
      visited[e.x][e.y] = 1;
    } else if (e.y < n - 1 && hasDirection(&e, DIRECTION_RIGHT) && a[e.x][e.y + 1] == 0 && !visited[e.x][e.y + 1]) {
      removeDirection(&e, DIRECTION_RIGHT);
      push(&steps, e);
      e.y++;
      e.directions = ALL_DIRECTIONS;
      removeDirection(&e, DIRECTION_LEFT);
      push(&steps, e);
      visited[e.x][e.y] = 1;
    } else if (e.x < m - 1 && hasDirection(&e, DIRECTION_DOWN)
        && a[e.x + 1][e.y] == 0 && !visited[e.x + 1][e.y]) {
      removeDirection(&e, DIRECTION_DOWN);
      push(&steps, e);
      e.x++;
      e.directions = ALL_DIRECTIONS;
      removeDirection(&e, DIRECTION_UP);
      push(&steps, e);
      visited[e.x][e.y] = 1;
    } else if (e.y > 0 && hasDirection(&e, DIRECTION_LEFT)
        && a[e.x][e.y - 1] == 0 && !visited[e.x][e.y - 1]) {
      removeDirection(&e, DIRECTION_LEFT);
      push(&steps, e);
      e.y--;
      e.directions = ALL_DIRECTIONS;
      removeDirection(&e, DIRECTION_RIGHT);
      push(&steps, e);
      visited[e.x][e.y] = 1;
    }
  }

  if (isEmpty(&steps)) {
    printf("No");
  } else {
    printf("Yes");
  }

  return 0;
}

追问

谢谢大神，最近没看到，等下试试

Answer 2

说一下我的想法吧
1 把初始点放入一个队列
2 出队列->获取该点的上下左右坐标，并且是有意义的坐标（不超出边界，不是障碍）
3 将 2 获取的点 判断是不是终点 是结束 不是继续
4 将 2 获取的点 加入队列 重复 234步骤

有些细节可以需要注意，可能你要排除重复的点不加入该队列 不然会造成上下点死循环本回答被网友采纳