# DS1ex1Note

{%hackmd theme-dark %}

## 簡介

:::info
任務一：
讀入存放一個迷宮的檔案，第一列為兩正整數 $X,Y$ 代表橫軸寬與縱軸長，第 $2 \sim Y+1$ 列每列有 $X$ 個字元組成 $X\times Y$ 的迷宮

接著從左上角開始往右走，直到遇到障礙物 $(O)$ 後就右轉，也就是按右下左上順序走直到走到目標 $(G)$ ，或是確定沒路走了就停止

最後輸出走過的位置，如果有找到往目標的路徑就輸出結果
:::
:::info

任務二：
讀入存放一個迷宮的檔案，第一列為兩正整數 $X,Y$ 代表橫軸寬與縱軸長，第 $2 \sim Y+1$ 列每列有 $X$ 個字元組成 $X\times Y$ 的迷宮，然後輸入一個自然數 $N$ 表示要找到 $N$ 個目標

接著從左上角開始往右走，直到遇到障礙物 $(O)$ 後就右轉，也就是按右下左上順序走直到走到 $N$ 個目標 $(G)$ ，或是確定沒路走了就停止

最後輸出走過的位置，如果有找到 $N$ 個目標的路徑就輸出結果

:::

---

## 解法

任務一：
直接按題目說的做就可以了，每走到一個點就紀錄這個位置有走過，然後先開一個stack或deque先臨時記下路徑，如果這條路可以走到終點就永久記下來然後停止，接著判斷原本的方向能不能繼續走(走過的路也不能再走)，不能就右轉直到有路可走，如果四個方向都試過了表示這條是死路，把當前的點從路徑中刪除然後回頭再試上一個點。

任務二：
跟任務一一樣，只是改成找到終點的話要繼續走直到找到所需數量的終點而已

## Flow Chart


---


---

## Pseudo Code

maze[x][y] := the cell at (x,y) of the maze.
cur_x, cur_y := current position.
cur_dir := current direction.
G := the number of remaining goals.
tmpP := an empty stack to store temporary path.
P := an array of empty stacks to store the paths to the goals.

func DFS(cur_x, cur_y): f, f is whether G is 0 or not.

	if G is 0:
		return SUCCESS
	end if
	if cur_x or cur_y exceeds the boundary:
		return FAIL
	end if
    
        if maze[cur_x][cur_y] is obstacle:
            return FAIL
        end if
    
	if maze[cur_x][cur_y] has been visited:
		return FAIL
	end if
	
	Mark maze[cur_x][cur_y] as visited.
	
	tmpP.push(maze[cur_x][cur_y])
	
	if maze[cur_x][cur_y] is a goal:
		P.push(tmpP)
		G := G - 1
	end if
	
	for k in [0, 3]:
		switch ( cur_dir ):
			case right:
				nxt_x := cur_x + 1
			case down:
				nxt_y := cur_y + 1
			case left:
				nxt_x := cur_x - 1
			case up:
				nxt_y := cur_y - 1
		end switch
		
		DFS( nxt_x, nxt_y )
		
		cur_dir := next direction
		
	end for
	
	tmpP.pop()
	
	return G is 0
end func

## 遇到的困難及解決方式

我認為最困難的地方是無法得知最終測試會用哪個版本的C\+\+編譯，string to integer 只能使用atoi()還是能用stoi()、vector of vector的宣告到底要不要在 `>>` 中間加空格，最後我選擇偏向C++11之前也就是很舊的版本的寫法來避開Dev Cpp在沒有加
`-std=c++11` 編譯參數的情況下發生 compile error