DFS（深度優先搜尋）

def dfs(node, visited=None):
    """
    Universal DFS template for trees and graphs
    Can be adapted for various problems
    """
    # Base case
    if not node or (visited and node in visited):
        return
    
    # Mark as visited (for graphs)
    if visited is not None:
        visited.add(node)
    
    # Process current node (pre-order position)
    process(node)
    
    # Recursive calls
    for neighbor in get_neighbors(node):
        dfs(neighbor, visited)
    
    # Post-order processing if needed
    # process_after(node)

# Preorder: Root -> Left -> Right
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Inorder: Left -> Root -> Right  
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Postorder: Left -> Right -> Root
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Iterative with Stack
def dfs_iterative(root):
    if not root:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Add right first so left is processed first (LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

LC 101 trace — root = [1,2,2,null,3,null,3]     helper(a, b) pairs  a.left <-> b.right
                                                                   a.right <-> b.left
        1               helper(a=2, b=2)                  vals equal -> descend
      /   \             |- helper(a.left=null, b.right=3)  exactly one null -> FALSE
    2       2           |- (never evaluated: `and` short-circuits)
     \       \
      3       3         answer = False
   a.right  b.right     <- both 3's are RIGHT children, so they are not mirror partners

straight pairing (a.left<->b.left, a.right<->b.right) on the same two inputs:

  [1,2,2,null,3,null,3]   null==null, then 3==3  -> True    (correct answer: False)
  [1,2,2,3,4,4,3]         3 vs 4                 -> False   (correct answer: True)

# python
# LC 101 - Symmetric Tree
# IDEA: paired (dual-pointer) DFS; recurse on the MIRROR pairing (a.left, b.right) / (a.right, b.left)
# time = O(n), space = O(h)   # h = tree height, worst O(n)
class Solution:
    def isSymmetric(self, root):
        if not root:
            return True
        # NOTE: the helper takes TWO nodes -> the root is never compared to anything
        return self.helper(root.left, root.right)

    def helper(self, left, right):
        if not left and not right:      # both empty -> mirrored
            return True
        if not left or not right:       # exactly one empty -> not mirrored
            return False
        if left.val != right.val:
            return False
        return (
            self.helper(left.left, right.right)     # outer pair
            and
            self.helper(left.right, right.left)     # inner pair
        )

// java
// LC 101 - Symmetric Tree
// IDEA: paired (dual-pointer) DFS; recurse on the MIRROR pairing
// time = O(n), space = O(h)
public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    return helper(root.left, root.right);
}

private boolean helper(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null) {
        return false;
    }
    if (left.val != right.val) {
        return false;
    }
    return helper(left.left, right.right)      // outer pair
            && helper(left.right, right.left); // inner pair
}

# python
# LC 101 - Symmetric Tree (iterative — the stated follow-up)
# IDEA: same mirror pairing, kept on an explicit stack; pop two entries = pop one pair
# time = O(n), space = O(n)
def isSymmetric(root):
    if not root:
        return True
    stack = [root.left, root.right]
    while stack:
        p, q = stack.pop(), stack.pop()          # NOTE: pops ONE pair
        if not p and not q:
            continue
        if not p or not q or p.val != q.val:
            return False
        # push the two mirror pairs
        stack.append(p.left)
        stack.append(q.right)                    # outer pair
        stack.append(p.right)
        stack.append(q.left)                     # inner pair
    return True

def dfs_graph(graph, start):
    """
    DFS for graph with cycle handling
    """
    visited = set()
    result = []
    
    def dfs(node):
        if node in visited:
            return
        
        visited.add(node)
        result.append(node)
        
        for neighbor in graph[node]:
            dfs(neighbor)
    
    dfs(start)
    return result

# For detecting cycles
def has_cycle(graph):
    visited = set()
    rec_stack = set()
    
    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True
        
        rec_stack.remove(node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

// java
// LC 419 - Battleships in a Board
// IDEA: a cell starts a NEW ship iff it is 'X' and has no 'X' above and no 'X' to its left
// time = O(M*N), space = O(1)
public int countBattleships(char[][] board) {
    int count = 0;
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            if (board[r][c] != 'X') continue;
            if (r > 0 && board[r - 1][c] == 'X') continue;   // continuation of a vertical ship
            if (c > 0 && board[r][c - 1] == 'X') continue;   // continuation of a horizontal ship
            count++;
        }
    }
    return count;
}

# python
# LC 419 - Battleships in a Board
# IDEA: count only the top-left cell of each ship -> no visited set needed
# time = O(M*N), space = O(1)
def countBattleships(board):
    count = 0
    for r in range(len(board)):
        for c in range(len(board[0])):
            if board[r][c] != 'X':
                continue
            if r > 0 and board[r - 1][c] == 'X':
                continue
            if c > 0 and board[r][c - 1] == 'X':
                continue
            count += 1
    return count

def find_paths(root, target):
    """
    Find all root-to-leaf paths with sum = target
    """
    def dfs(node, curr_sum, path, result):
        if not node:
            return
        
        # Update current state
        curr_sum += node.val
        path.append(node.val)
        
        # Check if leaf and target met
        if not node.left and not node.right:
            if curr_sum == target:
                result.append(path[:])
        
        # Explore children
        dfs(node.left, curr_sum, path, result)
        dfs(node.right, curr_sum, path, result)
        
        # Backtrack
        path.pop()
    
    result = []
    dfs(root, 0, [], result)
    return result

private boolean dfsPathVisitor(int node, int destination, Map<Integer, List<Integer>> map, boolean[] visited) {
    if (node == destination) return true;

    visited[node] = true;

    for (int next : map.get(node)) {
        if (!visited[next]) {
            // ❌ WRONG: Ignoring return value - continues searching even after path found!
            dfsPathVisitor(next, destination, map, visited);
        }
    }

    return false;  // Will ALWAYS return false (except for direct hits)
}

private boolean dfsPathVisitor(int node, int destination, Map<Integer, List<Integer>> map, boolean[] visited) {
    if (node == destination) return true;

    visited[node] = true;

    for (int next : map.get(node)) {
        if (!visited[next]) {
            // ✅ CORRECT: Return immediately when path found!
            if (dfsPathVisitor(next, destination, map, visited)) {
                return true;
            }
        }
    }

    return false;  // Only return false if ALL paths explored
}

Graph: 0 -- 1 -- 2 -- 3
       |         |
       4 -------- 5

Adjacency List:
0: [1, 4]
1: [0, 2]
2: [1, 3, 5]
3: [2]
4: [0, 5]
5: [2, 4]

Task: Find path from 0 to 3

1. dfsPathVisitor(0, 3, ..., visited=[])
   → visited = [0]
   → Loop neighbors: [1, 4]

   2. dfsPathVisitor(1, 3, ..., visited=[0])  // First neighbor
      → visited = [0, 1]
      → Loop neighbors: [0, 2]  (skip 0, already visited)

      3. dfsPathVisitor(2, 3, ..., visited=[0,1])
         → visited = [0, 1, 2]
         → Loop neighbors: [1, 3, 5]  (skip 1)

         4. dfsPathVisitor(3, 3, ..., visited=[0,1,2])
            → ✅ Found! Returns TRUE

         ← Returns TRUE to level 3

      ← But level 2 IGNORES the return value!
      ← Continues checking neighbor 5

      5. dfsPathVisitor(5, 3, ..., visited=[0,1,2])
         → visited = [0, 1, 2, 5]
         → Loop neighbors: [2, 4]  (both visited)
         ← Returns FALSE

      ← Level 2 finishes loop, returns FALSE

   ← Level 1 receives FALSE from neighbor 1

   6. dfsPathVisitor(4, 3, ..., visited=[0,1,2,5])  // Second neighbor
      → visited = [0, 1, 2, 5, 4]
      → Loop neighbors: [0, 5]  (both visited)
      ← Returns FALSE

   ← Level 0 finishes loop, returns FALSE

❌ FINAL RESULT: FALSE (Path exists but not detected!)

1. dfsPathVisitor(0, 3, ..., visited=[])
   → visited = [0]
   → Loop neighbors: [1, 4]

   2. dfsPathVisitor(1, 3, ..., visited=[0])  // First neighbor
      → visited = [0, 1]
      → Loop neighbors: [0, 2]  (skip 0)

      3. dfsPathVisitor(2, 3, ..., visited=[0,1])
         → visited = [0, 1, 2]
         → Loop neighbors: [1, 3, 5]  (skip 1)

         4. dfsPathVisitor(3, 3, ..., visited=[0,1,2])
            → ✅ Found! Returns TRUE

         ← Returns TRUE to level 3

      ← Level 2 checks: if (TRUE) return true;  ✅
      ← Returns TRUE immediately (skips remaining neighbors!)

   ← Level 1 checks: if (TRUE) return true;  ✅
   ← Returns TRUE immediately (skips neighbor 4!)

✅ FINAL RESULT: TRUE (Correct!)

// Use when: "Does path exist?" "Can we reach?" "Is there a route?"
if (dfs(next)) {
    return true;  // Found one path - that's enough!
}

// Use when: "Find ALL paths" "Count all solutions" "Collect all combinations"
dfs(next);  // Don't return early - need to explore all branches

def backtrack_template(candidates, target):
    """
    General backtracking template
    """
    def backtrack(start, path, remaining):
        # Base case - found solution
        if remaining == 0:
            result.append(path[:])
            return
        
        # Try all possibilities
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                continue
            
            # Make choice
            path.append(candidates[i])
            
            # Recurse
            backtrack(i, path, remaining - candidates[i])
            
            # Undo choice (backtrack)
            path.pop()
    
    result = []
    backtrack(0, [], target)
    return result

def modify_tree(root, condition):
    """
    Modify tree structure based on condition
    """
    if not root:
        return None
    
    # Recursively modify subtrees first
    root.left = modify_tree(root.left, condition)
    root.right = modify_tree(root.right, condition)
    
    # Modify current node based on condition
    if not condition(root):
        # Example: delete node, return child
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Handle two children case
        # ... (find successor/predecessor)
    
    return root

// java
// LC 199
private TreeNode _dfs(TreeNode node){

    if (node == null){
        return null;
    }

    /** NOTE !!! no need to create global node, but can define inside the method */
    TreeNode root2 = node;
    root2.left = this._dfs(node.left);
    root2.right = this._dfs(node.right);

    /** NOTE !!! we need to return root as final step */
    return root2;
}

def bottom_up_dfs(root):
    """
    Process subtrees first, then current node
    Useful for subtree problems
    """
    def dfs(node):
        if not node:
            return 0  # or base value

        # Process subtrees first
        left_result = dfs(node.left)
        right_result = dfs(node.right)

        # Process current node using subtree results
        current_result = process(node, left_result, right_result)

        # Update global result if needed
        self.global_result = max(self.global_result, current_result)

        return current_result

    self.global_result = 0
    dfs(root)
    return self.global_result

# python
# LC 124 - Binary Tree Maximum Path Sum
# IDEA: post-order DFS; record the `turning` path globally, return the best `straight` path upward
# time = O(n), space = O(h)   # h = tree height, worst O(n)
class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')

        def dfs(node):
            if not node:
                return 0
            left = max(0, dfs(node.left))       # drop a negative subtree
            right = max(0, dfs(node.right))     # drop a negative subtree
            # (1) candidate: path TURNS here, uses BOTH children -> global only
            self.max_sum = max(self.max_sum, left + right + node.val)
            # (2) upward: path CONTINUES, so only ONE child may be kept
            return max(left, right) + node.val

        dfs(root)
        return self.max_sum

// java
// LC 124 - Binary Tree Maximum Path Sum
// IDEA: post-order DFS; record the `turning` path globally, return the best `straight` path upward
// time = O(n), space = O(h)
private int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxSum = Integer.MIN_VALUE;
    dfs(root);
    return maxSum;
}

private int dfs(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = Math.max(0, dfs(node.left));    // drop a negative subtree
    int right = Math.max(0, dfs(node.right));  // drop a negative subtree
    maxSum = Math.max(maxSum, left + right + node.val);  // turns here
    return Math.max(left, right) + node.val;             // continues upward
}

# python
# LC 124 - Binary Tree Maximum Path Sum (no-clamp variant)
# IDEA: a negative branch restarts at root.val, so both sides carry root.val -> subtract one copy
# time = O(n), space = O(h)
def dfs(node):
    if not node:
        return 0
    l_max, r_max = dfs(node.left), dfs(node.right)
    l_max = node.val if l_max < 0 else l_max + node.val
    r_max = node.val if r_max < 0 else r_max + node.val
    self.maximum = max(self.maximum, l_max + r_max - node.val)   # NOTE: `- node.val`
    return max(l_max, r_max)

LC 979 trace — root = [0, 3, 0]        balance = val - 1 + left + right

        0                 dfs(left  3) -> 3 - 1 + 0 + 0 = +2   moves += 2   (2 coins go UP)
       / \                dfs(right 0) -> 0 - 1 + 0 + 0 = -1   moves += 1   (1 coin  goes DOWN)
      3   0               dfs(root  0) -> 0 - 1 + 2 + (-1) = 0            <- always 0 at root

  total moves = 2 + 1 = 3

# python
# LC 979 - Distribute Coins in Binary Tree
# IDEA: post-order DFS; each subtree returns its net balance, each edge costs |balance| moves
# time = O(n), space = O(h)   # h = tree height, worst O(n)
class Solution:
    def distributeCoins(self, root):
        self.moves = 0

        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)                 # net surplus/deficit of left subtree
            right = dfs(node.right)               # net surplus/deficit of right subtree
            balance = node.val - 1 + left + right # keep 1 coin, push the rest up
            self.moves += abs(balance)            # this subtree's edge to its parent
            return balance                        # NOTE: signed, never abs()

        dfs(root)
        return self.moves

// java
// LC 979 - Distribute Coins in Binary Tree
// IDEA: post-order DFS; each subtree returns its net balance, each edge costs |balance| moves
// time = O(n), space = O(h)
private int moves = 0;

public int distributeCoins(TreeNode root) {
    moves = 0;
    dfs(root);
    return moves;
}

private int dfs(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = dfs(node.left);
    int right = dfs(node.right);
    int balance = node.val - 1 + left + right;  // keep 1 coin, push the rest up
    moves += Math.abs(balance);                 // this subtree's edge to its parent
    return balance;                             // NOTE: signed, never Math.abs()
}

// java
// LC 1254
// V0
// IDEA: 2-Pass DFS (Boundary Elimination)
/**
 * Algorithm:
 * Pass 1: Start from all boundary cells and flood-fill to eliminate
 *         all islands connected to the boundary (these cannot be closed)
 * Pass 2: Count remaining land cells as closed islands
 *
 * Time: O(m×n), Space: O(m×n) for recursion stack
 */
public int closedIsland(int[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }

    int rows = grid.length;
    int cols = grid[0].length;

    // Pass 1: Eliminate boundary-connected islands
    // Flood top and bottom borders
    for (int c = 0; c < cols; c++) {
        flood(grid, 0, c);           // Top border
        flood(grid, rows - 1, c);    // Bottom border
    }

    // Flood left and right borders
    for (int r = 0; r < rows; r++) {
        flood(grid, r, 0);           // Left border
        flood(grid, r, cols - 1);    // Right border
    }

    // Pass 2: Count closed islands
    int count = 0;
    for (int r = 1; r < rows - 1; r++) {
        for (int c = 1; c < cols - 1; c++) {
            if (grid[r][c] == 0) {
                count++;
                flood(grid, r, c);  // Mark entire island
            }
        }
    }

    return count;
}

private void flood(int[][] grid, int r, int c) {
    int rows = grid.length;
    int cols = grid[0].length;

    // Base case: out of bounds or water
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 1) {
        return;
    }

    grid[r][c] = 1;  // Mark land as water (visited)

    // Flood 4-directionally
    flood(grid, r + 1, c);
    flood(grid, r - 1, c);
    flood(grid, r, c + 1);
    flood(grid, r, c - 1);
}

# python
# LC 1254
def closedIsland(grid):
    """
    2-Pass DFS approach
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])

    def flood(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 1:
            return
        grid[r][c] = 1
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)

    # Pass 1: Eliminate boundary islands
    for c in range(cols):
        flood(0, c)
        flood(rows - 1, c)

    for r in range(rows):
        flood(r, 0)
        flood(r, cols - 1)

    # Pass 2: Count closed islands
    count = 0
    for r in range(1, rows - 1):
        for c in range(1, cols - 1):
            if grid[r][c] == 0:
                count += 1
                flood(r, c)

    return count

// Java implementation with directional encoding
public int numDistinctIslands(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }

    Set<String> uniqueIslandShapes = new HashSet<>();
    int rows = grid.length;
    int cols = grid[0].length;

    // Iterate through every cell in the grid
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            // Start DFS only on unvisited land cells
            if (grid[r][c] == 1) {
                StringBuilder pathSignature = new StringBuilder();
                // Start DFS from (r, c). 'S' marks the start
                dfs(grid, r, c, pathSignature, 'S');

                if (pathSignature.length() > 0) {
                    uniqueIslandShapes.add(pathSignature.toString());
                }
            }
        }
    }

    return uniqueIslandShapes.size();
}

/**
 * DFS with directional encoding
 * Records the direction taken to reach each cell
 * Uses 'O' delimiter when backtracking
 */
private void dfs(int[][] grid, int r, int c, StringBuilder path, char direction) {
    int rows = grid.length;
    int cols = grid[0].length;

    // Base cases: Out of bounds or water/visited
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0) {
        return;
    }

    // 1. Mark as visited by setting to 0
    grid[r][c] = 0;

    // 2. Record the direction taken to reach this cell
    path.append(direction);

    // 3. Recurse in FIXED order (Down, Up, Right, Left)
    dfs(grid, r + 1, c, path, 'D');  // Down
    dfs(grid, r - 1, c, path, 'U');  // Up
    dfs(grid, r, c + 1, path, 'R');  // Right
    dfs(grid, r, c - 1, path, 'L');  // Left

    // 4. Add delimiter when backtracking
    // This distinguishes different branch structures
    path.append('O');
}

def count_distinct_shapes(grid):
    """
    Count distinct island shapes using path signatures
    Key: Encode each island's shape as a unique string
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    unique_shapes = set()

    def dfs(r, c, r0, c0, path):
        """
        DFS with path signature encoding
        r0, c0: Starting position for relative encoding
        path: StringBuilder to record the shape signature
        """
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return

        # Mark as visited
        grid[r][c] = 0

        # Encode relative position
        path.append(f"({r - r0},{c - c0})")

        # Visit neighbors in FIXED order (critical for consistency)
        dfs(r + 1, c, r0, c0, path)  # Down
        dfs(r - 1, c, r0, c0, path)  # Up
        dfs(r, c + 1, r0, c0, path)  # Right
        dfs(r, c - 1, r0, c0, path)  # Left

    # Iterate through grid in fixed order (top-left to bottom-right)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                path = []
                dfs(r, c, r, c, path)  # Start with (r, c) as origin
                unique_shapes.add(tuple(path))

    return len(unique_shapes)

# python — LC 1219
# GUARD lives at the top of the child → doubles as the recursion base case.
# Cleanest to reason about: you may call dfs() on ANY coordinate (even off-grid);
# the child rejects itself. Cost: every invalid neighbor still spends one call frame.
class Solution:
    def getMaximumGold(self, grid):
        self.max_gold = 0
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] > 0:
                    self.dfs(grid, r, c, 0)   # start value = 0
        return self.max_gold

    def dfs(self, grid, r, c, cur_gold):
        rows, cols = len(grid), len(grid[0])
        # (1) GUARD: out of bounds OR empty(0) OR visited(-1) → stop
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] <= 0:
            return
        cache = grid[r][c]
        cur_gold += cache                                  # (2) ACCUMULATE here
        self.max_gold = max(self.max_gold, cur_gold)       # (3) UPDATE MAX per cell entry
        grid[r][c] = -1                                    # mark visited
        # recurse into ALL 4 dirs unconditionally — guard filters at the top
        self.dfs(grid, r + 1, c, cur_gold)
        self.dfs(grid, r - 1, c, cur_gold)
        self.dfs(grid, r, c + 1, cur_gold)
        self.dfs(grid, r, c - 1, cur_gold)
        grid[r][c] = cache                                 # BACKTRACK: restore

# python — LC 1219
# GUARD is inline BEFORE each recursive call → no wasted frames on invalid neighbors.
# The launch loop's `if grid[y][x] > 0` validates the START cell (child no longer does).
class Solution:
    def getMaximumGold(self, grid):
        self.max_gold = 0
        L, W = len(grid), len(grid[0])
        for y in range(L):
            for x in range(W):
                if grid[y][x] > 0:
                    self.dfs(grid, x, y, grid[y][x])   # start value = the cell itself
        return self.max_gold

    def dfs(self, grid, x, y, cur_gold):
        L, W = len(grid), len(grid[0])
        self.max_gold = max(self.max_gold, cur_gold)   # (3) UPDATE MAX per cell entry — safe
        cache = grid[y][x]
        grid[y][x] = -1                                # mark visited
        moves = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        for dx, dy in moves:
            x_, y_ = x + dx, y + dy
            # (1) GUARD before recursing  +  (2) ACCUMULATE at the call site
            if 0 <= x_ < W and 0 <= y_ < L and grid[y_][x_] > 0:
                self.dfs(grid, x_, y_, cur_gold + grid[y_][x_])
        grid[y][x] = cache                             # BACKTRACK: restore

# python — LC 1219
# Same structure as V0-2, BUT max_gold is updated INSIDE the loop (on `next_gold`),
# not at cell entry. Consequence: the entry cell is never scored by the DFS itself,
# so a lone gold cell with no gold neighbors would be missed → the launch loop must
# SEED max_gold with grid[y][x]. That extra dependency is exactly what makes it fragile.
class Solution:
    def getMaximumGold(self, grid):
        self.max_gold = 0
        L, W = len(grid), len(grid[0])
        for y in range(L):
            for x in range(W):
                if grid[y][x] > 0:
                    self.max_gold = max(self.max_gold, grid[y][x])  # ⚠️ REQUIRED seed
                    self.dfs(grid, x, y, grid[y][x])
        return self.max_gold

    def dfs(self, grid, x, y, cur_gold):
        L, W = len(grid), len(grid[0])
        cache = grid[y][x]
        grid[y][x] = -1                                # mark visited (once per frame)
        moves = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        for dx, dy in moves:
            x_, y_ = x + dx, y + dy
            if 0 <= x_ < W and 0 <= y_ < L and grid[y_][x_] > 0:
                # NOTE: do NOT mark/unmark grid[y][x] here inside the loop.
                # Marking is per-cell-entry, not per-neighbor: the same cell is
                # explored by all 4 branches of THIS frame; re-marking each
                # iteration would corrupt the shared state.
                next_gold = cur_gold + grid[y_][x_]
                self.max_gold = max(self.max_gold, next_gold)   # (3) UPDATE MAX in loop
                self.dfs(grid, x_, y_, next_gold)
        grid[y][x] = cache                             # BACKTRACK: restore

# 399 Evaluate Division
# there is also an "union find" solution
class Solution:
    def calcEquation(self, equations, values, queries):
        from collections import defaultdict
        # build graph
        graph = defaultdict(dict)
        for (x, y), v in zip(equations, values):
            graph[x][y] = v
            graph[y][x] = 1.0/v
        ans = [self.dfs(x, y, graph, set()) for (x, y) in queries]
        return ans

    def dfs(self, x, y, graph, visited):
        if not graph:
            return
        if x not in graph or y not in graph:
            return -1
        if x == y:
            return 1
        visited.add(x)
        for n in graph[x]:
            if n in visited:
                continue
            visited.add(n)
            d = self.dfs(n, y, graph, visited)
            if d > 0:
                return d * graph[x][n]
        return -1.0

// java
// V1
// IDEA: DFS
// https://leetcode.com/problems/evaluate-division/solutions/3543256/image-explanation-easiest-concise-comple-okpu/
public double[] calcEquation_1(List<List<String>> equations, double[] values, List<List<String>> queries) {
    HashMap<String, HashMap<String, Double>> gr = buildGraph(equations, values);
    double[] finalAns = new double[queries.size()];

    for (int i = 0; i < queries.size(); i++) {
        String dividend = queries.get(i).get(0);
        String divisor = queries.get(i).get(1);

        /** NOTE !!!
         *
         *  either dividend nor divisor NOT in graph, return -1.0 directly
         */
        if (!gr.containsKey(dividend) || !gr.containsKey(divisor)) {
            finalAns[i] = -1.0;
        } else {

            /** NOTE !!!
             *
             *  we use `vis` to check if element already visited
             *  (to avoid repeat accessing)
             *  `vis` init again in every loop
             */

            HashSet<String> vis = new HashSet<>();
            /**
             *  NOTE !!!
             *
             *   we init `ans` and pass it to dfs method
             *   (but dfs method return NOTHING)
             *   -> `ans` is init, and pass into dfs,
             *   -> so `ans` value is updated during dfs recursion run
             *   -> and after dfs run completed, we get the result `ans` value
             */
            double[] ans = { -1.0 };
            double temp = 1.0;
            dfs(dividend, divisor, gr, vis, ans, temp);
            finalAns[i] = ans[0];
        }
    }

    return finalAns;
}

/** NOTE !!! below dfs method */
public void dfs(String node, String dest, HashMap<String, HashMap<String, Double>> gr, HashSet<String> vis,
                double[] ans, double temp) {

    /** NOTE !!! we use `vis` to check if element already visited */
    if (vis.contains(node))
        return;

    vis.add(node);
    if (node.equals(dest)) {
        ans[0] = temp;
        return;
    }

    for (Map.Entry<String, Double> entry : gr.get(node).entrySet()) {
        String ne = entry.getKey();
        double val = entry.getValue();
        /** NOTE !!! update temp as `temp * val` */
        dfs(ne, dest, gr, vis, ans, temp * val);
    }
}

public HashMap<String, HashMap<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
    HashMap<String, HashMap<String, Double>> gr = new HashMap<>();

    for (int i = 0; i < equations.size(); i++) {
        String dividend = equations.get(i).get(0);
        String divisor = equations.get(i).get(1);
        double value = values[i];

        gr.putIfAbsent(dividend, new HashMap<>());
        gr.putIfAbsent(divisor, new HashMap<>());

        gr.get(dividend).put(divisor, value);
        gr.get(divisor).put(dividend, 1.0 / value);
    }

    return gr;
}

DFS Problem Analysis Flowchart:

1. Is it a tree/graph traversal problem?
   ├── YES → Check structure type
   │   ├── Tree? → Use Tree Templates (1, 3, 5, 6)
   │   │   ├── Need specific order? → Template 1 (Traversal)
   │   │   ├── Need paths? → Template 3 (Path Finding)
   │   │   ├── Need to modify? → Template 5 (Modification)
   │   │   └── Need subtree info? → Template 6 (Bottom-up)
   │   └── Graph? → Use Graph Template (2)
   │       ├── Has cycles? → Add visited set
   │       ├── Need all paths? → Track path
   │       └── Multi-source? → Start from all sources
   └── NO → Continue to 2

2. Is it a combinatorial problem?
   ├── YES → Use Backtracking Template (4)
   │   ├── Permutations? → Swap elements
   │   ├── Combinations? → Start index
   │   ├── Subsets? → Include/exclude
   │   └── Constraint satisfaction? → Check validity
   └── NO → Continue to 3

3. Does it require exploring all possibilities?
   ├── YES → Use DFS with appropriate state tracking
   │   ├── Grid problem? → 4-directional DFS
   │   ├── String problem? → Index-based DFS
   │   └── Decision tree? → Choice-based DFS
   └── NO → Consider different algorithm

4. Special considerations:
   ├── Need shortest path? → Consider BFS instead
   ├── Has optimal substructure? → Consider DP
   └── Need all solutions? → DFS with backtracking