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’，分別代表上、下、左、右四個方向
- 無需處理輸出