Description
給定一張包含鬼魂座標、目的地座標的地圖資訊，請試著利用以下的演算機制，幫鬼魂找到一條通往目的地的道路。（此路徑不一定為最短路徑）
(Reference: https://www.youtube.com/watch?v=ataGotQ7ir8&ab_channel=RetroGameMechanicsExplained)
演算法運作機制如下：
-
已知鬼魂位置、鬼魂移動方向、目的地位置
-
依序（上、左、下、右）檢查鬼魂在當前位置可以走的所有合法方向。不合法的方向包含：
(1)會撞到障礙物的方向
(2)往回走的方向（當前鬼魂移動方向的反方向）
-
若有不止一個方向是合法方向，確認移動方向與目標點的水平或垂直軸交點間是否有障礙物，若其中一個移動方向沒有障礙物，則選擇該者；若多個移動方向皆沒有障礙物，則選擇沒有障礙物且往合法移動方向前進一格後，與目標點之間的直線距離最短者（同上一條規則）；若皆有障礙物，則選擇往合法移動方向前進一格後，與目標點之間的直線距離最短者（同上一條規則）；若多個合法方向離目標點的距離一樣，則按上、左、下、右的順序選擇。
以上圖為例說明：
上圖合法方向包括向右和向上，向右的方向延伸至與目標垂直軸的交點有障礙物，而向上的方向延伸與目標點水平軸的交點沒有障礙物，所以依照上述規則，即使向右移動一格後，與目標點之間的直線距離小於向上移動一格後，與目標點之間的直線距離，也會選擇向上移動（沒有障礙物）
-
根據步驟3，將鬼魂的座標往該方向移動一格
-
檢查鬼魂位置是否為目的地位置。若是則代表找到路徑、程式結束；若否則返回步驟2
此題將提供主要執行程式main.c (題號.c)、以及Header檔function.h (題號.h)。請試著完成Header檔中未實現的函式：CheckIsValidDirection()、CalculateDistance()
Methods:
- void FindPath2Target() – 透過傳入的地圖資訊、鬼魂位置、目的地位置，使用上述演算機制，輸出一條可到達目的地的路徑。(無須實作，但希望同學能理解程式碼，對真正實作專案有幫助！)
- int CheckIsValidDirection() – 透過傳入的地圖資訊、鬼魂位置、鬼魂移動方向，判斷鬼魂往該方向移動是否會穿越邊界、或撞到障礙物。若不會則回傳1，反之回傳0
- double CalculateDistance() – 透過傳入的鬼魂位置、目的地位置，計算並回傳兩個位置點之間的直線距離
function.c
#include "function.h"
int CheckIsValidDirection(char map[ROW][COL], int g_r, int g_c, enum Direction dir)
{
// TODO
}
double CalculateDistance(int g_r, int g_c, int t_r, int t_c)
{
// TODO
}
Input
一個6x6的地圖資訊，輸入符合以下格式
c c c c c c
c c c c c c
c c c c c c
c c c c c c
c c c c c c
c c c c c c
Note:
-
‘-’代表空格、’X’代表障礙物、’g’代表鬼魂的位置、’t’代表目的地的位置
-
並不會有無法到達目的地的側資
-
無需處理輸入
Output
輸出符合以下格式：
CCCCCCC...
Note:
-
輸出的最後必須要有一個換行符號 (“\n”)
-
C可能為’U’、’D’、’L’、’R’，分別代表上、下、左、右四個方向
-
無需處理輸出