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
輸出符合以下格式：
DDDDDD...
Note:
- 輸出的最後必須要有一個換行符號 ('\n')
- D可能為’U’、’D’、’L’、’R’，分別代表上、下、左、右四個方向
- 無需處理輸出