#include<cstdio>
#pragma warning (disable:4996)
using namespace std;

int map[5][5];					//用来存储地图
int visit[5][5];				//用来标记每个坐标是否访问过
int direction[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };			//控制上右下左
int lastIndex;					//队列中最后一个状态的下标

struct Node						//存储每个节点
{
	int x, y;					//坐标
	int fatherIndex;			//当前节点的上一个节点在队列中的下标，方便回溯
}queue[20];

void bfs()
{
	Node now, next;										//当前状态
	int head = 0, tail = 1;								//队列头尾指针
	now.x = 0;	now.y = 0;	now.fatherIndex = 0;		//初始化状态
	visit[0][0] = 1;									//要记得将起点标记为已访问
	queue[0] = now;										//初始状态入队

	while (head < tail)									//只要队列不为空
	{
		now = queue[head];								//队列头出队
		head++;											//头指针后移一个
			
		for (int i = 0; i < 4; i++)						//四个方向尝试，将可能到达的下一个节点都加入队列
		{
			int dx = now.x + direction[i][0];			//下一个节点的坐标
			int dy = now.y + direction[i][1];
			
			if ((0 <= dx && dx < 5) && (0 <= dy && dy < 5) && (map[dx][dy] == 0) && (visit[dx][dy] == 0))	//在不越界的前提下，下一个节点可走且未被访问过，则加入队列
			{
				visit[dx][dy] = 1;						//标记已访问

				next.x = dx;							//更新下一个节点的坐标
				next.y = dy;
				next.fatherIndex = head - 1;			//前一个节点在队列中的位置就是出队元素的下标，也就是头指针所指的前一个
				
				//printf("(%d,%d)--->(%d,%d)   fatherIndex=%d\n", now.x, now.y, next.x, next.y, next.fatherIndex);

				queue[tail] = next;						//下一个节点入队
				tail++;									//队尾后移一个

				if ((next.x == 4) && (next.y == 4))		//若下一个节点是终点
				{
					lastIndex = tail - 1;				//记录最后一个节点在队列中的下标
					//printf("lastIndex=%d\n", lastIndex);
					return;								//直接结束bfs
				}	
			}
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			scanf("%d", &map[i][j]);		//读取地图，并清空状态数组
			visit[i][j] = 0;
		}
	}

	bfs();

	int trace_x[20], trace_y[20];			//记录横坐标、纵坐标
	int count = 0;
	

	for (int index = lastIndex; index > 0;)		//由最后一个Node往前找，第一个的下标在数组中一定是第一个
	{
		trace_x[count] = queue[queue[index].fatherIndex].x;
		trace_y[count] = queue[queue[index].fatherIndex].y;
		//printf("(%d,%d)\n", trace_x[count], trace_y[count]);
		count++;
		index = queue[index].fatherIndex;		//不断更新当前节点在队列中的下标，回溯上一个节点
	}
	
	for (int i = count - 1; i >= 0; --i)
	{
		printf("(%d, %d)\n", trace_x[i], trace_y[i]);
	}
	printf("(4, 4)\n");

	return 0;
}

• Re:数组模拟队列，详细注释 (2546) 20122002048 2021-04-15 10:15:08