jmu資料結構實驗任務

選做：題目5—走迷宮

總時間限制: 1000ms 記憶體限制: 65536kB

描述

一個迷宮由R行C列格子組成，有的格子里有障礙物，不能走；有的格子是空地，可以走，
給定一個迷宮，求從左上角走到右下角最少需要走多少步(資料保證一定能走到)，只能在水平方向或垂直方向走，不能斜著走，

輸入

第一行是兩個整數，Ｒ和Ｃ，代表迷宮的長和寬，（ 1<= R，C <= 40)
接下來是Ｒ行，每行Ｃ個字符，代表整個迷宮，
空地格子用'.'表示，有障礙物的格子用'#'表示，
迷宮左上角和右下角都是'.'，

輸出

輸出從左上角走到右下角至少要經過多少步（即至少要經過多少個空地格子），計算步數要包括起點和終點，

樣例輸入

5 5
..###
#....
#.#.#
#.#.#
#.#..

樣例輸出

9

題解

先將輸入的迷宮外圍加上一圈“#”方便判斷

如：

..###
#....
#.#.#
#.#.#
#.#..
//題目輸入的迷宮

#######
#..####
##....#
##.#.##
##.#.##
##.#..#
#######
//外圈補上“#”的迷宮

找到起點(1,1)點將起點加入存盤搜索起點的佇列，并將起點步數標注為1，從搜索起點（此時為起點(1,1)）開始向上下左右四個方向進行搜索，如果為“.”則將該點加入佇列，將該點標注為已經到過，同時將該點步數標注為搜索起點的步數+1，

四個方向搜索完后，將起點從佇列中移除，對佇列中的下一個點進行相同操作，直到遇到終點(c,r),回傳到該點的步數，

代碼

#include<iostream>
#include<queue>
using namespace std;
int goxy[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };//左右下上四個方向
char Map[42][42];//儲存迷宮
bool went[42][42];//保存已經到達的點，將已經到達的點標注為1；
typedef struct position
{
	int x;
	int y;
}pos;//坐標
int bfs(int r, int c)
{
	int stair[42][42][1];//保存點的步數
	int x, y;
	queue<pos>now;//儲存搜索起點的佇列
	now.push({ 1,1 });//將起點加入存盤搜索起點的佇列
	went[1][1] = 1;//將起點標記為已到達
	stair[1][1][0] = 1;//將起點步數標注為1
	do
	{
		x = now.front().x;
		y = now.front().y;//佇列中的當前點
		for (int i = 0; i < 4; i++)//四個方向開始搜索
		{
			if (Map[x + goxy[i][0]][y + goxy[i][1]] == '.' && !went[x + goxy[i][0]][y + goxy[i][1]])//判斷該點是否滿足條件
			{
				now.push({ x + goxy[i][0],y + goxy[i][1] });//將符合條件的點加入佇列
				went[x + goxy[i][0]][y + goxy[i][1]] = 1;//將該點標注為已到過
				stair[x + goxy[i][0]][y + goxy[i][1]][0] = stair[x][y][0] + 1;//將該點步數標注為搜索起點的步數+1
				if (x + goxy[i][0] == c && y + goxy[i][1] == r)//判斷是否遇到終點
				{
					x = c; y = r;//如果遇到終點，將當前點更換為終點
					break;
				}
			}
		}
		now.pop();//將當前搜索起點出隊
	} while (x != c || y != r);
	return stair[x][y][0];//回傳終點的步數
}
int main()
{
	int r, c;
	cin >> r >> c;
	for (int i = 1; i <= c; i++)
	{
		for (int j = 1; j <= r; j++)
		{
			cin >> Map[i][j];
		}
	}
	//將輸入的迷宮外圍加上一圈“#”方便判斷
	for (int j = 0; j <= r + 1; j++)
	{
		Map[0][j] = '#';
		Map[c + 1][j] = '#';
	}
	for (int i = 0; i <= c + 1; i++)
	{
		Map[i][0] = '#';
		Map[i][r + 1] = '#';
	}
	cout << bfs(r, c);
	return 0;
}

由于老師額外要求要判斷無法到達終點的情況

因此修改代碼：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int goxy[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };//左右下上四個方向
char Map[42][42];//儲存迷宮
bool went[42][42];//保存已經到達的點，將已經到達的點標注為1；
typedef struct position
{
	int x;
	int y;
}pos;//坐標
int bfs(int r, int c)
{
	int stair[42][42][1];//保存點的步數
	int x, y;
	queue<pos>now;//儲存搜索起點的佇列
	memset(stair, 0, sizeof(stair));//初始化所有步數為0
	now.push({ 1,1 });//將起點加入存盤搜索起點的佇列
	went[1][1] = 1;//將起點標記為已到達
	stair[1][1][0] = 1;//將起點步數標注為1 
	do
	{
		x = now.front().x;
		y = now.front().y;//佇列中的當前點
		for (int i = 0; i < 4; i++)//四個方向開始搜索
		{
			if (Map[x + goxy[i][0]][y + goxy[i][1]] == '.' && !went[x + goxy[i][0]][y + goxy[i][1]])//判斷該點是否滿足條件
			{
				now.push({ x + goxy[i][0],y + goxy[i][1] });//將符合條件的點加入佇列
				went[x + goxy[i][0]][y + goxy[i][1]] = 1;//將該點標注為已到過
				stair[x + goxy[i][0]][y + goxy[i][1]][0] = stair[x][y][0] + 1;//將該點步數標注為搜索起點的步數+1
				if (x + goxy[i][0] == c && y + goxy[i][1] == r)//判斷是否遇到終點
				{
					x = c; y = r;//如果遇到終點，將當前點更換為終點
					break;
				}
			}
		}
		now.pop();//將當前搜索起點出隊
	} while ((x != c || y != r) && !now.empty());
	return stair[c][r][0];//回傳終點的步數
}
int main()
{
	int r, c, stair;
	cin >> r >> c;
	for (int i = 1; i <= c; i++)
	{
		for (int j = 1; j <= r; j++)
		{
			cin >> Map[i][j];
		}
	}
	//將輸入的迷宮外圍加上一圈“#”方便判斷
	for (int j = 0; j <= r + 1; j++)
	{
		Map[0][j] = '#';
		Map[c + 1][j] = '#';
	}
	for (int i = 0; i <= c + 1; i++)
	{
		Map[i][0] = '#';
		Map[i][r + 1] = '#';
	}
	stair = bfs(r, c);
	if (stair)
		cout << stair;
	else
		cout << "NO";
	return 0;
}

在搜索開始時將所有點的步數設為0，搜索完后如果終點步數依然為0，則說明沒有路徑到達終點，輸出“NO”，

測驗樣例

5 5

....#

##.##

..###

##.##

####.

樣例輸出

???NO