內容
給你一個 NXN 格的迷宮, 迷宮中以#代表障礙物, 以.代表路, 你固定在(2,2)出發, 目的地是(n-1,n-1), 求包括起點和終點, 最少路徑的長度。
輸入
N(N 不超過 100)
N 行 N 列由#和.組成的迷宮
9
##########
#.......##
#.#####.##
#.......##
##.#.#####
#..#.#..##
#.##.##.##
#.......##
#########
輸出
一個正整數, 代表最短路徑的長度, 如果不可能到達終點, 則印出 No solution!
13
解題思路
基礎 BFS 題目，因為測資不大所以直接在矩陣上模擬 Dijkstra 演算法
具體流程如下 :
- 先把地圖導入二維陣列，障礙物設成-1，空地設為任一最大步驟數(邊長 * 邊長)不會達到的極大值。
- 將起點位置設為 1
- 遍歷整個陣列，如果遇到 1 就將它周圍大於 1 的數字改為 2
- 繼續遍歷，遇到 2 就將它周圍大於 2 的數字改為 3
- 之後同理，不斷遍歷陣列直到終點不為極大值即是答案。
由於題目有可能會有無法抵達終點的情況，所以如果遍歷完一輪但陣列沒有發生改變就代表已經沒有路了，跳出迴圈並輸出”No solution!”。
完整程式碼
AC (4ms, 112KB)
#include <stdio.h>
#define MAX 2147483647
int table[100][100];
int main()
{
int n, end, now;
char tmp, moving;
while (scanf(" %d", &n) == 1)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
scanf(" %c", &tmp);
table[i][j] = tmp == '#' ? -1 : MAX;
}
}
end = n - 2, now = 0, moving = table[1][1] = 1;
while (table[end][end] == MAX && moving)
{
moving = 0, now++;
for (int i = 1; i <= end; i++)
{
for (int j = 1; j <= end; j++)
{
if (table[i][j] == now)
{
if (table[i][j + 1] > now) table[i][j + 1] = now + 1;
if (table[i][j - 1] > now) table[i][j - 1] = now + 1;
if (table[i + 1][j] > now) table[i + 1][j] = now + 1;
if (table[i - 1][j] > now) table[i - 1][j] = now + 1;
moving = 1;
}
}
}
}
if (moving)
printf("%d\n", table[end][end]);
else
puts("No solution!");
}
return 0;
}
|
