用BFS廣度優先搜索在迷宮裡搜尋最短路徑 (C++)

這個...在這裡發不知道對不對...
恩...首先祝大家新年快樂
如題,假如迷宮長這樣:

.S.#.
##.#.
.....
.####
....F

要從S開始找最短路徑到F,"#"是牆壁而"."是可以走的地方,規定要用1D array來做,所以我有一個很長的array裡面的數值是這迷宮每一行的資料
i.e array[1] = S 而
array[24] = F , 找到最短路徑之後可以走的地方"."要替換成星號"*"

我現在只做到讀取檔案把檔案的2D迷宮轉成1D array... BFS毫無頭緒
首先我是不是該先搜尋這個array的S在哪裡? 要如何找?

然後那路徑...是不是該建立另外一個array來記錄我走過的地方,該怎麼做哩...然後很明顯每一步並不是只有一個選擇又該怎麼把那些我不要的選擇弄掉哩?


algorithm跟想法/解釋,如果能有code輔助更好!

謝謝大家!