队列进行迷宫求解

解题思路:

顺序队列使用数组固定容量，从起点进入并标记为-1，代表已访问，出队一个方块e检查是否是终点，若是终点则反向回溯输出完整路径，若不是则寻找四个方向可通行的方块。

关键代码：
struct Box
{
public int i, j;
public int pre;
}
class SqQueue
{
public Box[] data;
public int front, rear;
public SqQueue(int maxSize) { data = new Box[maxSize]; front = rear = -1; }
public bool IsEmpty() => front == rear;
public void EnQueue(Box e) => data[++rear] = e;
public Box DeQueue() => data[++front];
}
static void PrintPath(SqQueue qu, int index)
{
if (index < 0) return;
PrintPath(qu, qu.data[index].pre);
Console.WriteLine($"({qu.data[index].i}, {qu.data[index].j})");
}
static bool MgPath(int xi, int yi, int xe, int ye, int[,] mg)
{
int M = mg.GetLength(0), N = mg.GetLength(1);
SqQueue qu = new SqQueue(M * N);
Box e = new Box { i = xi, j = yi, pre = -1 };
qu.EnQueue(e);
mg[xi, yi] = -1;

int[] di = { -1, 0, 1, 0 };
int[] dj = { 0, 1, 0, -1 };

while (!qu.IsEmpty())
{
e = qu.DeQueue();
if (e.i == xe && e.j == ye)
{
PrintPath(qu, qu.front);
return true;
}

for (int dir = 0; dir < 4; dir++)
{
int ni = e.i + di[dir];
int nj = e.j + dj[dir];
if (ni >= 0 && ni < M && nj >= 0 && nj < N && mg[ni, nj] == 0)
{
Box next = new Box { i = ni, j = nj, pre = qu.front };
qu.EnQueue(next);
mg[ni, nj] = -1;
}
}
}
return false;
}

clone地址：https://github.com/LMingHao-study/-