【LeetCode】DFS

今天出去玩，买了好多东西，只想赶快把这篇赶出来。

DFS：碰到一个新节点时，先从这个新节点开始往下做，所以用 FILO 的 stack or 等价的递回来做。
通常是走遍 matrix，但 tree 的 3 种 traversal 也算是 dfs

1. 通常外层来判断哪个位置开始要做 dfs，
   然後再 call 内层的 dfs function

for 所有元素:
    if 条件成立:
        dfs(x, y)

2. 纪录 visited
   通常会需要纪录已经拜访的元素，或是更改原来的元素做标记，以避免重复访问造成无穷回圈
   额外纪录 visited 会占空间，但面试时要先厘清是否可以更改原先的 input。

3. 判断 bound
   个人习惯是
   递回时：无论如何先走下一步，再从最前面的 basic case 判断是否越界
   迭代时：先判断下一步是否越界，才决定是否加进 stack。

4. 方向
   若是经典的走 matrix 的四个方向，可以用 directions = [-1, 0, 1, 0, -1]，每相临两个代表一个方向。

695. Max Area of Island (Medium)
79. Word Search (Medium)

dfs 的实作，包含怎麽利用已经找到的结果（例如 79），都会影响整体速度。
可以多参考别人的 code 测看看哪里比较快，
而且因为模式都很相像，可以写一个自己最喜欢的版本的 pseudo code，方便以後把熟悉度练上去。

小结

.. 好想睡觉ㄛ
本来想写 trie 和 graph 却一直拖