def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:

        # Note:
        # Fewest operations to reach a target value
        # using a Bounded Implicit Number-Line Graph

        # Values:
        # nums = [1, 2], start = 3, goal = 6

        # Legal Operations From x:
        # x + num, x - num, x ^ num, for every num in nums


        # BFS Over The Implicit "Current Value Of x" Graph

        # Each integer in [0, 1000] is a node in an implicit graph, with
        # no literal graph built up front. An edge connects value v to
        # v + num, v - num, and v ^ num for every num in nums, since
        # each is a single legal operation.

        # BFS explores values level by level:
        #   - the first time goal is reached
        #   - that level number is guaranteed to be the minimum number
        #     of operations.

        # BFS State Encoding:
        #   - each queued item tracks a single piece of info:
        #       - x => the current value reached so far

        # Legal Next Move:
        #   - From a state (x),
        #   - x + num, x - num, and x ^ num are all legal for every num in nums
        #   - but only results landing inside [0, 1000] can be used, 
        #     since operations beyond that range are terminal
        #   - Values outside [0, 1000] are still valid endpoints if they equal goal, 
        #     just not continuable.

        # Safety Insight:
        #   - Once a value has been visited, we know BFS has already
        #     reached it via the fewest possible operations, so we can
        #     safely skip requeuing it.

        # Edge Case:
        # already at the target with zero operations
        if start == goal:
            return 0

        # Iterative BFS Queue:
        # seed the queue with start, 0 operations taken so far
        queue = deque([start])

        # Self Edges and Parallel Edges Safety Tracking:
        #    - mark starting value as visited
        # sc: O(1001)
        visitedNum = {start}

        # BFS Depth Level
        #   - tracking min num of operations used to reach current depth level
        ops = 0

        while queue:

            ops += 1

            # Level By Level Expansion:
            #   - drain entire current level before incrementing ops
            #   - guarantees for every value discovered in this pass to
            #     have the same number of operations (depth) from start
            for _ in range(len(queue)):

                # Value previous jump:
                x = queue.popleft()

                # Explore Neighbors:
                # apply all 3 operations against every number in nums
                # tc: O(m), where m is len(nums)
                for num in nums:
                    for nextX in (x+num, x-num, x^num):

                        # Check:
                        # if goal reached, we are guaranteed to have
                        # the minimum number of operations, even if
                        # this endpoint falls outside [0, 1000]
                        if nextX == goal:
                            return ops

                        # Bounded Continuation:
                        # enque new state (nextX) if within [0, 1000]
                        # and not already visitedNum, since operations
                        # beyond that range are terminal
                        if 0 <= nextX <= 1000 and nextX not in visitedNum:
                            visitedNum.add(nextX)
                            queue.append(nextX)

        # All reachable in-range values processed without hitting
        # goal, no sequence of operations can reach it

        # overall: tc O(1001 * m), where m is len(nums), since each of
        #   the at most 1001 in-range values is expanded once, trying
        #   all 3 operations against every number in nums
        # overall: sc O(1001), for the visited set bounded by the fixed
        #   [0, 1000] range of continuable states
        return -1

Sol 1: Shortest Path Unweighted Graph BFS
1. (dead = set(deadends))
2. if "0000" in dead: 
    return -1
3. (queue = deque([("0000", 0)]))
4. (visited = set(["0000"]))
5. while queue:
   a. (state, moves) = queue.popleft()
   b. if state == target: 
        return moves
   c. for i in range(4):
      digit = int(state[i])
      for change in (-1, 1):
         new_digit = (digit + change) % 10
         newState = state[:i] + str(new_digit) + state[i+1:]
         if newState not in visited and newState not in dead:
            visited.add(newState)
            queue.append((newState, moves + 1))
6. return -1

    def openLock(self, deadends: List[str], target: str) -> int:
        
        # BFS over the lock's state graph

        # Each 4-digit combination is represented as a node in an implicit graph,
        # meaning there is no literal grid/list to build, 
        # but instead states are generated on the fly.
        # An edge connects two states if one wheel-turn transforms one into another,
        # as each of the 4 wheels can turn +1 or -1 with wraparound 0 <-> 9
        # BFS explores states level by level, so the first time a 'target' is dequeued,
        # it is guaranteed to be the shortest number of turns
        

        # Dead end states set
        # sc: O(n)
        dead = set(deadends)
        
        # Edge Case:
        # If starting position is a dead end, we cannot move.
        if "0000" in dead:
            return -1
        
        # Iterative BFS Queue:
        # set starting position as "0000" as begin exploring
        queue = deque([("0000", 0)])
        visited = set(["0000"])
        
        while queue:

            # Pop a state from the queue
            state, moves = queue.popleft()
            
            # Check:
            # if target reached, we are guaranteed to have minimum number of moves
            if state == target:
                return moves
            
            # Explore Neighbors:
            # turn all 4 wheels in +/- 1 directions
            for i in range(4):

                # pick 1 of the 4 wheels
                digit = int(state[i])
                
                # Two possible rotations:
                # +1 and -1 (with wraparound)
                for rotate in (-1, 1):
                    
                    new_digit = (digit + rotate) % 10
                    
                    # Grab original wheel digits, 
                    # except for the one we just rotated
                    newState = (state[:i] + str(new_digit) + state[i+1:])
                    
                    # Early Pruning:
                    # only queue state if:
                    # - not visited
                    # - not a dead end
                    if newState not in visited and newState not in dead:
                        
                        visited.add(newState)
                        queue.append((newState, moves + 1))

        # Exhausted all possible rotation combinations without finding target

        # overall: tc O(10^4)
        # overall: sc O(10^4)
        return -1

Sol 1: Shortest Path Unweighted Graph BFS
1. (bankSet = set(bank))
2. if endGene not in bankSet: 
    return -1
3. (gene_chars = ['A', 'C', 'G', 'T'])
4. (queue = deque([(startGene, 0)]))
5. visited = {startGene}
6. while queue:
   a. (geneString, mutations) = queue.popleft()
   b. if geneString == endGene: Return mutations
   c. for i in range(len(geneString)):
      for c in gene_chars:
         if c == geneString[i]: continue
            rotatedGene = geneString[:i] + c + geneString[i+1:]
         if rotatedGene in bankSet and rotatedGene not in visited:
            visited.add(rotatedGene)
            queue.append((rotatedGene, mutations + 1))
7. return -1

    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        
        # BFS over the gene mutation graph

        # Each gene string combination is represented as a node in an implicit graph,
        # meaning there is no literal grid/list to build, 
        # but instead states are generated on the fly.
        # An edge connects two states if one gene slot modification transforms
        # one into another, as there are 4 possible gene letters.
        # BFS explores states level by level, so the first time a 'target' is dequeued,
        # it is guaranteed to be the shortest number of turns
        # as well as guaranteed to have all possible gene combinations
        
        
        # Turn valid gene list into set
        # sc: O(n)
        bankSet = set(bank)

        # Edge Case:
        # endGene is not reachable, no transformation sequence exists
        if endGene not in bankSet:
            return -1

        # All gene slot chars
        gene_chars = ['A', 'C', 'G', 'T']

        # Iterative BFS Queue
        queue = deque([(startGene, 0)])

        # Tracking 
        # sc: O(n^4)
        visited = {startGene}

        while queue:

            
            geneString, mutations = queue.popleft()

            # Reached target gene:
            # Ensured we have taken the minimum number of steps to get to
            # the final combination, which implies we have all possible previous 
            # combinations in the mutations list
            if geneString == endGene:
                return mutations

            # Modify each gene slot
            for i in range(len(geneString)):

                # Explore Neighbor:
                # Replace each gene slot with all other 3 genes
                for c in gene_chars:

                    # Skip original gene
                    if c == geneString[i]:
                        continue

                    # Grab all original gene slots, 
                    # except for the slot we just modified
                    rotatedGene = geneString[:i] + c + geneString[i + 1:]

                    # Early Pruning:
                    # Only queue mutations that are valid (in bank) and unseen
                    if rotatedGene in bankSet and rotatedGene not in visited:
                        visited.add(rotatedGene)
                        queue.append((rotatedGene, mutations + 1))

        # Exhausted all reachable mutations without finding endGene

        # overall: tc O(n)
        # overall: sc O(n)
        return -1

Sol 1: Shortest Path Unweighted Graph BFS
1. (wordSet = set(wordList))
2. if endWord not in wordSet: 
        return 0
3. (letters = 'abcdefghijklmnopqrstuvwxyz')
4. (queue = deque([(beginWord, 1)]))
5. (visited = set([beginWord]))
6. while queue:
   a. ((word, steps) = queue.popleft())
   b. if word == endWord: 
       return steps
   c. for i in range(len(word)):
      for c in letters:
         if c == word[i]: 
            continue
         newWord = word[:i] + c + word[i+1:]
         if newWord in wordSet and newWord not in visited:
            queue.append((newWord, steps+1))
            visited.add(newWord)
7. return -1

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        
        # BFS over the word transformation graph

        # Each word is represented as a node in an implicit graph,
        # meaning there is no literal grid/list to build,
        # but instead states are generated on the fly.
        # An edge connects two words if they differ by exactly one letter
        # as each of the L letter slots can be swapper to any of the other 25 letters
        # BFS explores states level by level, so the first time 'endWord' is dequeued,
        # it is guaranteed to be reached via the shortest transformation sequence

        # Valid word list as a set
        # sc: O(V)
        wordSet = set(wordList)

        # Empty Check: 
        # endWord is not reachable, no transformation sequence exists
        # tc: O(1)
        if endWord not in wordSet:
            return 0

        # All possible letters for each slot
        letters = 'abcdefghijklmnopqrstuvwxyz'

        # Iterative BFS Queue:
        # set starting position as beginWord, sequence steps starts at 1
        # (LeetCode counts the beginWord itself as the first word in the sequence)
        queue = deque([(beginWord, 1)])
        visited = set([beginWord])

        while queue:

            # Pop a transformation
            word, steps = queue.popleft()

            # Check:
            # if endWord reached, we are guaranteed to have the minimum sequence steps
            if word == endWord:
                return steps

            # Explore Neighbors:
            # swap every letter slot to every other possible letter
            # tc: O(L)
            for i in range(len(word)):

                # Grab original letter,
                # except for the one we're about to swap
                for c in letters:

                    # Skip original letter
                    if c == word[i]:
                        continue

                    # New transformation
                    newWord = word[:i] + c + word[i + 1:]

                    # Early Pruning:
                    # - not in wordSet, invalid word
                    # - already visited, we reached this via a shorter sequence
                    if newWord in wordSet and newWord not in visited:

                        # queue new valid transformation
                        queue.append((newWord, steps+1))
                        visited.add(newWord)

        # Exhausted all possible transformations without finding endWord

        # overall: tc O(n * L^2), where n = len(wordList), l = len(beginWord)
        #   for each word popped, we try l slots * 26 letters = O(l * 26),
        #   and each candidate word construction/hashing costs O(l)
        # overall: sc O(n * L), for the wordSet/visited set storing up to n words of steps l
        return -1

    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:


        # Note:
        # Shortest cycle length in an undirected graph
        # using BFS Rooted At Every Node

        # Edge List:
        # edges = [[0,1],[1,2],[2,0],[1,3],[3,4],[4,1]]

        # Adjacency List:
        # adj = {
        #         0: [1, 2],
        #         1: [0, 2, 3, 4],
        #         2: [1, 0],
        #         3: [1, 4],
        #         4: [3, 1],
        #       }


        # BFS From Every Node To Detect The Shortest Cycle

        # Unlike a single-source shortest path, there's no fixed start
        # or target here, a cycle can pass through any node, so each
        # node in turn is treated as a BFS root. From a given root, BFS
        # assigns every reachable node a distance and a parent edge.

        # BFS explores nodes level by level:
        #   - whenever BFS reaches an already-visited node through an
        #     edge that isn't the one it arrived by
        #   - that means two distinct paths from the root converge
        #     there, and their combined length forms a cycle back
        #     through the root.

        # BFS State Encoding:
        #   - each queued item tracks a single piece of info:
        #       - node => the current node being expanded
        #   - dist[node]   => distance from root to node
        #   - parent[node] => the node used to first reach node

        # Legal Next Move:
        #   - From a state (node),
        #   - every adjacent edge is explored except the one leading
        #     back to parent[node],
        #   - since that edge was just used to arrive and isn't a
        #     cycle candidate back to itself.

        # Safety Insight:
        #   - Once a node has been visited from a given root, we know
        #     BFS has already recorded its shortest distance from that
        #     root, so a second arrival at it (via a non-parent edge)
        #     can only mean a cycle, never a shorter path.

        # Build Adjacency List:
        # build once and reused as the neighbor lookup for every root's
        # BFS, rather than rescanning edges each time
        # tc: O(V + E)
        adj = defaultdict(list)
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        # Result Initialization:
        # infinity signals no cycle found yet, shrunk as shorter
        # cycles are discovered across every root tried
        shortest = float('inf')

        # Try Every Node As Root:
        # a cycle's shortest detection is only guaranteed if BFS is run
        # from a node actually on it, so every node must be tried
        # tc: O(V)
        for root in range(n):

            # Distance And Parent Tracking:
            # dist[-1] doubles as "unvisited"; parent tracks which node
            # was used to reach a node, so that same edge can be
            # excluded when checking for a cycle-closing edge
            # sc: O(V)
            dist = [-1] * n
            parent = [-1] * n
            dist[root] = 0

            # Iterative BFS Queue:
            # seed the queue with root, 0 edges used so far
            queue = deque([root])

            while queue:

                # Node previous jump:
                node = queue.popleft()

                # Explore Neighbors:
                # apply every edge out of the current node
                for neighbor in adj[node]:

                    # Skip Parent Edge:
                    # the edge just used to arrive at node should not be
                    # treated as a cycle candidate back to itself
                    if neighbor == parent[node]:
                        continue

                    # First Visit:
                    # unvisited neighbor extends the BFS tree normally
                    if dist[neighbor] == -1:
                        dist[neighbor] = dist[node] + 1
                        parent[neighbor] = node
                        queue.append(neighbor)

                    else:
                        # Cycle Detected:
                        # neighbor was already reached by a different
                        # path from root, so this edge closes a cycle
                        # whose length is both distances plus this edge
                        shortest = min(shortest, dist[node] + dist[neighbor] + 1)

        # All roots processed, shortest now holds the minimum cycle
        # length found across every BFS tree, or infinity if none exist

        # overall: tc O(V * (V + E)), since a full BFS is run once per
        #   vertex as root, each costing O(V + E)
        # overall: sc O(V + E), for the adjacency list plus the dist
        #   and parent arrays reused across each root's BFS
        return shortest if shortest != float('inf') else -1

    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:

        # Note:
        # Shortest path where edges must strictly alternate color
        # using two separate Edge Lists

        # Edge Lists:
        # redEdges  = [[0, 1], [1, 2]]
        # blueEdges = [[2, 0]]

        # Adjacency Lists By Color:
        # redAdj  = { 0: [1], 1: [2] }
        # blueAdj = { 2: [0] }


        # BFS Over The (Node, Last Edge Color) State Graph
        # - plain node to node BFS can't enforce alternation, 
        #   since whether a given edge is legal to take next depends on the
        #   color of the edge used to arrive. 
        # - So each state here is a pair (node, last color used), 
        #   and an edge in this augmented graph only exists 
        #   if its color differs from the color that led to the current state.

        # BFS explores states level by level:
        #   - the first time a node is reached via either color
        #   - that level number is guaranteed to be its shortest alternating path.

        # BFS State Encoding:
        #   - each queued item tracks two pieces of info:
        #       - node      => the current graph node
        #       - lastColor => the color of the edge used to arrive here
        #                      (0 = RED, 1 = BLUE)

        # Legal Next Move:
        #   - From a state (node, lastColor), 
        #   - only edges of the opposite color are legal to take next, 
        #   - since the path must strictly alternate colors on every step.

        # Self Edges and Parallel Edges Safety:
        #   - Once a (node, color) state has been visited, we know BFS has
        #     already reached it via the shortest possible path for that
        #     color, so we can safely skip requeuing it.

        # Build Adjacency Lists By Color:
        #   - separate red and blue edges up front, 
        #     so the neighbor lookup during BFS only ever considers edges of the color needed
        # tc: O(E)
        redAdj = defaultdict(list)
        for u, v in redEdges:
            redAdj[u].append(v)

        blueAdj = defaultdict(list)
        for u, v in blueEdges:
            blueAdj[u].append(v)

        # Res:
        #   - (-1) signals unreached until BFS proves otherwise; 
        #   - node 0 is always reachable from itself in 0 moves
        # sc: O(n)
        res = [-1] * n
        res[0] = 0

        # Color Constants:
        # 0 = RED, 1 = BLUE, used to track which color was last taken
        # into a node, since the same node can be reached via both
        # colors at potentially different distances
        RED, BLUE = 0, 1

        # Iterative BFS Queue:
        #   - seed both color states from node 0, since the very first move
        #     can legally be either color
        queue = deque([(0, RED), (0, BLUE)])

        # Self Edges and Parallel Edges Safety Tracking:
        #    - mark starting node as visited with both colors
        visited = {(0, RED), (0, BLUE)}

        # BFS Depth Level
        #   - tracking min num of steps to reach current nodes depth devel
        steps = 0

        while queue:

            steps += 1

            # Level By Level Expansion:
            #   - drain entire current level before incrementing steps
            #   - guarantees for every node discovered in this pass to have 
            #     the same number of steps (depth) from node 0
            for _ in range(len(queue)):

                # Node previous jump:
                node, lastColor = queue.popleft()

                # Grab Possible Opposite Color Moves:
                #   - mark next jump
                if lastColor == RED:
                    nextColor = BLUE
                else:
                    nextColor = RED

                # Grab the correct adjacency list:
                #   - switch colors from dequed node previous jump
                if nextColor == BLUE:
                    nextAdj = blueAdj
                else:
                    nextAdj = redAdj

                # Explore Neighbors:
                #   - only the opposite color's edges are legal next, since
                #     the path must strictly alternate
                #   - we do not nee
                for neighbor in nextAdj[node]:

                    # Early Pruning:
                    #   - enque new state (node, color) if not already visited
                    if (neighbor, nextColor) not in visited:
                        visited.add((neighbor, nextColor))
                        queue.append((neighbor, nextColor))

                        # First Discovery Recording:
                        #   - whichever color state reaches a node first
                        #     gives its true shortest alternating distance,
                        #   - only record it the first time it's seen
                        if res[neighbor] == -1:
                            res[neighbor] = steps

        # All reachable (node, color) states processed, remaining -1s
        # mean no valid alternating path exists to that node

        # overall: tc O(n + E)
        # overall: sc O(n + E)
        return res

    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:

        # Note:
        # Fewest bus boardings to reach a target stop using a Stop To Routes Map

        # Hyperedge List:
        #   - each route is a hyperedge connecting a group of nodes, 
        #     instead of just directly node to node

        #   - routes = [
        #               [1, 2, 7], 
        #               [3, 6, 7]
        #              ]
        
        # Stop To Routes Map:
        #   - derived bridge structure, maps {stop -> routes servicing it}
        #   - this will reveal if routes share a stop, 
        #     even if they do not belong to the same hyperedge
        
        # stopToRoutes = {
        #                  1: {0},
        #                  2: {0},
        #                  7: {0, 1},
        #                  3: {1},
        #                  6: {1},
        #                }

        # Implicit Route Graph:
        #   - the real graph BFS traverses, where each node is a route (getting on a bus)
        #     and two routes are adjacent if they share at least one stop

        # BFS Over The Bus Route Graph

        #   - rather than treating the stops as nodes,
        #     we treat the route themselves as nodes
        #   - two routes share are edge/are adjacent if they share at least one stop,
        #     since hopping on a bus to a shared stop allows you to transfer bus routes 

        # BFS explores routes level by level:
        #   - the first time a route containing target stop is reached,
        #     those number of bus transfers is guaranteed to be the min num required

        # BFS State Encoding:
        #   - (routeIdx, busCount)
        #   - routeIdx => the current route (hyperedge) being ridden
        #   - busCount => the number of buses transfers to reach it

        # Legal Next Move:
        #   - From a state (routeIdx, busCount),
        #     only routes sharing a stop with routeIdx are legal to transfer to

        # Safety Insight:
        #   - Once a route has been visited, 
        #     we know BFS has already reached it via the fewest possible boardings,
        #     so we can safely skip requeuing it.
        #   - Once a stop has been visited, 
        #     every route servicing it has already been queued, 
        #     so revisiting the stop can never surface a route worth expanding again.


        # ----------------------------
        # BFS Set up:

        # Edge Case:
        # already at the target without boarding any bus
        if source == target:
            return 0

        # Build Stop To Routes:
        #   - stop -> routes
        #   - allows for exploring what routes are available at a certain stop
        #   - checks what hyperedge a stop is connected to
        # tc: O(n) 
        stopToRoutes = defaultdict(set)
        for routeIdx, route in enumerate(routes):
            for stop in route:
                stopToRoutes[stop].add(routeIdx)

        # Unreachable:
        #   - if stop has no routes assigned (new or in the middle of no where),
        #     then stop is unreachable
        # tc: O(1)
        if target not in stopToRoutes:
            return -1

        # Self Edges and Parallel Edges Safety Tracking:

        #   - avoid visiting a stop twice if we have found the shortest path already
        visitedStops = {source}

        #   - mark visiting a route twice if we have found the shortest path already
        # sc: O(s)
        visitedRoutes = set()

        # Iterative BFS Queue:
        #   - for the starting route, put all stops that serve it
        queue = deque()
        for routeIdx in stopToRoutes[source]:
            queue.append((routeIdx, 1))
            visitedRoutes.add(routeIdx)

        while queue:

            # Route previous jump:
            routeIdx, busCount = queue.popleft()

            # Target Check:
            #   - if this route services target, 
            #     guaranteed to have the min num of bus transfers
            if target in routes[routeIdx]:
                return busCount

            # Explore Neighbors:
            #   - for each stop along this route,
            #     see what new routes are explorable by transferring at those stops
            for stop in routes[routeIdx]:

                # Visit Stop Once Pruning:
                #   - only add a new stop if not already visited
                #   - first time a stop is added, is guaranteed to be shortest transfers
                if stop not in visitedStops:

                    # mark stop as visited
                    visitedStops.add(stop)

                    # For each route at that stop
                    for nextRouteIdx in stopToRoutes[stop]:

                        # Visit Route Once Pruning:
                        #   - only add new route state if not already visited,
                        #   - first time a route is added, is guaranteed to be shortest transfers
                        if nextRouteIdx not in visitedRoutes:

                            # mark route as visited
                            visitedRoutes.add(nextRouteIdx)

                            # add exploration
                            queue.append((nextRouteIdx, busCount + 1))

        # All reachable routes processed without finding target,
        # no sequence of buses can reach it.
        
        # you are stranded

        # overall: tc O(n + s)
        # overall: sc O(n + s)
        return -1

Sol 1: Shortest Path Unweighted Graph BFS
1. if source == target: 
    a. return 0
2. (sourceSum = source[0] + source[1])
3. (targetSum = target[0] + target[1])
3. if sourceSum % 2 != targetSum % 2: 
    a. return -1
4. directions = [(-1,-1), (-1,1), (1,-1), (1,1)]
5. queue = deque([(source[0], source[1], 0)])
6. visited = set([(source[0], source[1])])
7. while queue:
   a. (row, col, moves) = queue.popleft()
   b. for each (dr, dc) in directions:
      r, c = row + dr, col + dc
      while 1 <= r <= 8 and 1 <= c <= 8:
         if [r, c] == target: return moves + 1
         if (r, c) not in visited:
            visited.add((r, c))
            queue.append((r, c, moves + 1))
         r, c = r + dr, c + dc
8. return -1

Sol 2: Closed Form Diagonal Parity Classification
1. (sr, sc = source)
2. (tr, tc = target)
2. if source == target: 
    a. return 0
3. if abs(sr - tr) == abs(sc - tc): 
    a. return 1
4. if (sr + sc) % 2 != (tr + tc) % 2: 
    a. return -1
5. return 2

    def minBishopMoves(self, source: list[int], target: list[int]) -> int:

        # BFS over the bishop's move graph

        # Each square on the 8x8 board is a node in an implicit graph.
        # Unlike the knight, a bishop's single move is an entire diagonal
        # slide: an edge connects source square (row, col) to every
        # square reachable by sliding in one of the 4 diagonal directions,
        # not just the adjacent cell. BFS still explores level by level,
        # so the first time target is reached, it is guaranteed to be
        # via the minimum number of moves.

        # Parity Pruning:
        # A bishop only ever visits squares of one color, determined by
        # the parity of (row + col). If source and target sit on
        # different colored squares, no sequence of moves can ever
        # connect them, so we can rule that out in O(1) before doing
        # any search at all.

        # Edge Case:
        # already at the target
        if source == target:
            return 0

        # different color squares, unreachable
        sourceSum = source[0] + source[1]
        targetSum = target[0] + target[1]
        if sourceSum % 2 != targetSum % 2:
            return -1

        # All 4 diagonal slide directions
        directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]

        # Iterative BFS Queue:
        # start at source, 0 moves taken
        queue = deque([(source[0], source[1], 0)])
        visited = {(source[0], source[1])}

        while queue:

            # Pop a position from the queue
            row, col, moves = queue.popleft()

            # Explore Neighbors:
            # apply all 4 diagonal directions, sliding as far as the
            # board allows in a single move
            for dr, dc in directions:

                # Try to step diagonally
                r, c = row + dr, col + dc

                # Check if diagonal step is in bounds:
                while 1 <= r <= 8 and 1 <= c <= 8:

                    # Diagonal step is valid, check if target 

                    # Target Check:
                    #   - guaranteed to have min num of moves
                    if [r, c] == target:
                        return moves + 1

                    # Early Pruning:
                    #   - no revisiting squares
                    if (r, c) not in visited:
                        visited.add((r, c))
                        queue.append((r, c, moves + 1))

                    # Continue try to shift diagonally
                    r, c = r + dr, c + dc

        # shouldn't reach here for same-color squares on a bounded board

        # overall: tc O(1)
        # overall: sc O(1)
        return -1

    def minBishopMoves(self, source: list[int], target: list[int]) -> int:

        # Closed-form case analysis over bishop reachability

        # A bishop's moves are fully characterized by two properties:
        # which diagonal it's on (row - col, for one direction, and
        # row + col for the other), and which color square it occupies
        # (parity of row + col). Rather than exploring the graph level
        # by level, we can classify the relationship between source and
        # target directly into one of four fixed outcomes, since on an
        # 8x8 board a bishop can always reach any same-colored square
        # in at most 2 moves.

        sr, sc = source
        tr, tc = target

        # Edge Case:
        # already at the target
        if source == target:
            return 0

        # Same Diagonal Check:
        # if source and target lie on the same diagonal, abs(row delta)
        # equals abs(col delta), so a single slide connects them directly
        if abs(sr - tr) == abs(sc - tc):
            return 1

        # Parity Pruning:
        # a bishop only ever visits squares of one color, determined by
        # the parity of (row + col). If source and target sit on
        # different colored squares, no sequence of moves can ever
        # connect them
        if (sr + sc) % 2 != (tr + tc) % 2:
            return -1

        # Fallback Case:
        # same color, not on a shared diagonal, so the bishop is not one
        # slide away. On a bounded 8x8 board this is always reachable in
        # exactly 2 moves, since some intermediate square lies on a
        # diagonal shared with both source and target

        # overall: tc O(1), only a fixed number of comparisons regardless of input
        # overall: sc O(1), no auxiliary data structures used
        return 2

Sol 1: Shortest Path Unweighted Graph BFS
1. x, y = abs(x), abs(y)
2. if x == 0 and y == 0: 
    return 0
3. moves = 8 knight move deltas
4. queue = deque([(0, 0, 0)])
5. visited = set([(0, 0)])
6. while queue:
   a. (cx, cy, moveCount) = queue.popleft()
   b. if cx == x and cy == y: Return moveCount
   c. for each (dx, dy) in moves:
      nx, ny = cx + dx, cy + dy
      if -2 <= nx <= x+2 and -2 <= ny <= y+2:
         if (nx, ny) not in visited:
            visited.add((nx, ny))
            queue.append((nx, ny, moveCount + 1))
7. return -1

    def minKnightMoves(self, x: int, y: int) -> int:
        
        # BFS over the knight's move graph

        # Each square on the infinite chessboard is represented as a node
        # in an implicit graph, meaning there is no literal grid/list to
        # build, but instead squares are generated on the fly.
        # An edge connects two squares if a single knight move (one of
        # the 8 "L" shaped jumps) transforms one into the other.
        # BFS explores squares level by level, so the first time (x, y)
        # is dequeued, it is guaranteed to be reached via the minimum
        # number of moves.

        # Symmetry Pruning:
        # The knight's movement is symmetric across both axes, a move
        # that reaches (x, y) can be mirrored to reach (-x, y), (x, -y),
        # or (-x, -y) in the same number of moves. So we only ever need
        # to search within the first quadrant (x >= 0, y >= 0), and take
        # the absolute value of the target up front. This roughly
        # quarters the search space compared to searching the full plane.

        # Normalize target into the first quadrant
        x, y = abs(x), abs(y)

        # Edge Case:
        # already at the target
        if x == 0 and y == 0:
            return 0

        # All 8 possible knight moves
        moves = [(-2, 1), (-1, 2), (1, 2), (2, 1),
                 (2, -1), (1, -2), (-1, -2), (-2, -1)]

        # Iterative BFS Queue:
        # start at origin, 0 moves taken
        queue = deque([(0, 0, 0)])
        visited = set([(0, 0)])

        while queue:

            # Pop a position from the queue
            cx, cy, moveCount = queue.popleft()

            # Check:
            # if target reached, we are guaranteed to have the minimum number of moves
            if cx == x and cy == y:
                return moveCount

            # Explore Neighbors:
            # apply all 8 possible knight moves
            for dx, dy in moves:

                nx, ny = cx + dx, cy + dy

                # Pruning Bound:
                # clamp exploration to a small buffer past the first quadrant,
                # since occasionally dipping to -1 or -2 is needed to route
                # around the target efficiently, but going further negative
                # or far beyond the target never helps
                if -2 <= nx <= x + 2 and -2 <= ny <= y + 2:

                    # Early Pruning:
                    # only queue position if not already visited
                    if (nx, ny) not in visited:

                        visited.add((nx, ny))
                        queue.append((nx, ny, moveCount + 1))

        # overall: tc O(max(x, y)^2), bounded search space after symmetry
        #   and pruning keeps the frontier close to the target region
        # overall: sc O(max(x, y)^2), for the visited set storing explored squares
        return -1

Sol 1: Shortest Path Unweighted Graph BFS
1. (rows, cols = width, height)
3. (entranceRow, entranceCol) = entrance
4. (queue = deque([(entranceRow, entranceCol, 0)]))
5. (visited = set([(entranceRow, entranceCol)]))
6. while queue:
   a. (row, col, steps) = queue.popleft()
   b. if steps > 0 and cell is on border:
        return steps
   c. for neighbor (nr, nc)
      if neighbor (nr, nc) bounds:
         if maze[nr][nc] == '.' and (nr, nc) not in visited:
            visited.add((nr, nc))
            queue.append((nr, nc, steps + 1))
7. return -1

    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        
        # BFS over the maze grid

        # Each cell is represented as a node in an implicit graph, the
        # grid itself acts as the adjacency structure, no separate
        # graph needs to be built.
        # An edge connects two cells if they're adjacent (up/down/left/right)
        # and the destination cell is empty ('.').
        # BFS explores cells level by level, so the first time a border
        # cell is dequeued, it is guaranteed to be reached via the
        # shortest number of steps.

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

        # 4 cardinal directions
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # Iterative BFS Queue:
        # start at entrance, 0 steps taken
        entranceRow, entranceCol = entrance
        queue = deque([(entranceRow, entranceCol, 0)])
        visited = set([(entranceRow, entranceCol)])

        while queue:

            # Pop a cell from the queue
            row, col, steps = queue.popleft()

            # Check:
            # if current cell is a border cell and not the entrance,
            # we are guaranteed to have the minimum number of steps
            # (entrance is excluded up front by only checking after the first pop)
            if steps > 0 and (row == 0 or row == rows - 1 or
                               col == 0 or col == cols - 1):
                return steps

            # Explore Neighbors:
            # move to all 4 adjacent cells
            for dr, dc in directions:

                nr, nc = row + dr, col + dc

                # Bounds Check:
                # stay within the grid
                if 0 <= nr < rows and 0 <= nc < cols:

                    # Early Pruning:
                    # only queue cell if:
                    # - not a wall
                    # - not already visited
                    if maze[nr][nc] == '.' and (nr, nc) not in visited:

                        visited.add((nr, nc))
                        queue.append((nr, nc, steps + 1))

        # Exhausted all reachable cells without finding a border exit

        # overall: tc O(m * n), each cell is visited and processed at most once
        # overall: sc O(m * n), for the visited set and queue storing up to every cell in the grid
        return -1

    def snakesAndLadders(self, board: List[List[int]]) -> int:

        # Note:
        # Fewest dice rolls to reach the final square using an implicit square number graph

        # Board Labeling:
        # squares are numbered 1 to n^2 in a boustrophedon (zigzag)
        # pattern, starting bottom-left, alternating direction each row

        # Board Labeling (n = 4):
        #
        #   16   15   14   13
        #    9   10   11   12
        #    8    7    6    5
        #    1    2    3    4

        # Legal Moves From curr:
        #   - up to 6 steps, depending on die role,
        #     curr+1, curr+2, ..., curr+6
        #   - if a snake/ladder destination it hit then do that

        # BFS Over The Implicit Square Number Graph
        #   - Each square from 1 to n^2 is a node in an implicit graph
        #   - Edge connects curr every square in [curr+1, curr+6]

        # BFS explores squares level by level:
        #   - the first time the final square (n^2) is reached,
        #     its guaranteed to have the min num of dice rolls

        # BFS State Encoding:
        #   - curr square num 

        # Legal Next Move:
        #   - From a state (curr), every square in [curr+1, curr+6] is legal, 
        #     bounded by the boards final square
        #   - and any snake/ladder destination is immediately resolved landed on is immediately resolved to its
        #     to its destination before being treated as a state.

        # Revisiting:
        #   - Once a square (post snake/ladder resolution) has been visited, 
        #     we know BFS has already reached it via the fewest possible rolls, so we can safely skip requeuing it.

        n = len(board)


        # Boustrophedon Flattening:
        #   - precompute a direct (cellNum -> (row, col) mapping once, 
        #     so the zigzag row direction logic is resolved up front 
        #     instead of being recomputed for every neighbor lookup during BFS

        # Boustrophedon Flattening (n = 4):
        #   - label layout (bottom-left start, zigzag):
        
        #   16   15   14   13
        #    9   10   11   12
        #    8    7    6    5
        #    1    2    3    4
        
        # Boustrophedon representation (n = 4):
        #   - board[row][col] indices (top-down, left-right):
        
        #                0     1     2     3
        # board[0] = [ (0,0) (0,1) (0,2) (0,3) ]   0
        # board[1] = [ (1,0) (1,1) (1,2) (1,3) ]   1
        # board[2] = [ (2,0) (2,1) (2,2) (2,3) ]   2
        # board[3] = [ (3,0) (3,1) (3,2) (3,3) ]   3

        # getCoords(6) => (2,2):
        #   row = (6-1)//4 = 1        <- boustrophedon row, counted from bottom, 0-indexed
        #   col = (6-1)%4  = 1        <- raw left-to-right offset within that row
        #   row % 2 == 1              -> odd row runs right-to-left, so flip: col = 4-1-1 = 2
        #   actualRow = 4-1-1 = 2     <- flip bottom-up row into top-down board row
        #   actualCol = 4-1-1 = 2     <- flip
        
        def cellNumToCoords(label):
            
            row = (label - 1) // n
            col = (label - 1) % n

            # Odd rows (counting from the bottom, 0-indexed) run
            # right-to-left, since the path alternates direction each row
            if row % 2 == 1:
                col = n - 1 - col

            # Board is indexed top-down, but labeling starts bottom-left
            actualRow = n - 1 - row

            return actualRow, col

        # Edge Case:
        # a 1x1 board starts and ends on the same square
        target = n * n
        if target == 1:
            return 0

        # Iterative BFS Queue:
        #   - init with square 1, with 0 rolls
        queue = deque([1])

        # Self Edges and Parallel Edges Safety Tracking:
        #    - mark starting square as visited
        # sc: O(n^2)
        visited = {1}

        # BFS Depth Level
        #   - tracking min num of dice rolls used to reach current depth level
        rolls = 0

        while queue:

            rolls += 1

            # Explore From Number Of Rolls:
            #   - from the current depth (dice rolls),
            #     explore the entire level before incrementing the rolls
            #   - guarantees for every square discovered in from this depth to next depth
            #     to have the same min number if rolls (depth)
            for _ in range(len(queue)):

                # Pick a square:
                curr = queue.popleft()

                # Explore Neighbors At The Number Of Rolls:
                #   - a single die roll can reach any square in the next 6,
                #     with a boundary at the last cell
                #   - need to do (+1) as the array is 1 indexed
                max6 = min(curr+6, target)
                for nextCellNum in range(curr+1, max6+1):

                    # Coords for next cell num
                    r, c = cellNumToCoords(nextCellNum)

                    # Snake/Ladder Resolution:
                    #   - if this square has a snake or ladder, 
                    #     the move actually lands on its destination instead,
                    #     applied exactly once per roll rather than chaining further
                    dest = board[r][c] if board[r][c] != -1 else next_

                    # Check:
                    #   - if we've reached the final square, we are
                    #     guaranteed to have the minimum number of rolls
                    if dest == target:
                        return rolls

                    # Early Pruning:
                    #   - only enqueue cell if not already visited
                    if dest not in visited:
                        visited.add(dest)
                        queue.append(dest)

        # All reachable squares processed without hitting target,
        # no sequence of rolls can reach it

        # overall: tc O(n^2)
        # overall: sc O(n^2)
        return -1

    def shortestPathAllKeys(self, grid: List[str]) -> int:

        # Note:
        # Fewest moves to collect all keys on a grid
        # using a (Position, Keys Bitmask) State Graph

        # Grid:
        # grid = ["@.a.#", "###.#", "b.A.B"]

        # Keys And Locks:
        # lowercase = key, uppercase = matching lock, '@' = start
        # a lock is only passable once its matching key bit is set


        # BFS Over The (Position, Keys Collected) State Graph

        # A plain cell-to-cell BFS can't work here, since whether a
        # lock can be crossed depends on which keys have been picked
        # up so far, and the same cell can legitimately be revisited
        # with a different key set. So each state here is a triple
        # (row, col, keysBitmask), and an edge exists between states if
        # a single cardinal move is legal, either because the destination
        # is open floor, a key (which updates the bitmask), or a lock
        # whose corresponding bit is already set.

        # BFS explores states level by level:
        #   - the first time a state with all keys collected is reached
        #   - that level number is guaranteed to be the minimum number
        #     of moves.

        # BFS State Encoding:
        #   - each queued item tracks three pieces of info:
        #       - row, col => the current position on the grid
        #       - keys     => bitmask of keys collected so far

        # Legal Next Move:
        #   - From a state (row, col, keys),
        #   - a cardinal move onto floor or a key is always legal,
        #   - a cardinal move onto a lock is legal only if keys already
        #     has that lock's matching bit set.

        # Safety Insight:
        #   - Once a (position, keys) state has been visited, we know
        #     BFS has already reached it via the shortest possible
        #     path for that exact key set, so we can safely skip
        #     requeuing it.

        m, n = len(grid), len(grid[0])
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # Locate Start And Count Keys:
        # scan once to find the starting cell and determine how many
        # total keys must be collected, since k is not given directly
        # tc: O(m * n)
        startRow, startCol = -1, -1
        totalKeys = 0
        for r in range(m):
            for c in range(n):
                cell = grid[r][c]
                if cell == '@':
                    startRow, startCol = r, c
                elif cell.islower():
                    totalKeys += 1

        # Target Bitmask:
        # all totalKeys bits set represents "every key collected"
        allKeysMask = (1 << totalKeys) - 1

        # Edge Case:
        # no keys exist on the board at all
        if totalKeys == 0:
            return 0

        # Iterative BFS Queue:
        # seed the queue with the start position and an empty key set
        start = (startRow, startCol, 0)
        queue = deque([start])

        # Self Edges and Parallel Edges Safety Tracking:
        #    - mark starting (position, keys) state as visited
        # sc: O(m * n * 2^k)
        visited = {start}

        # BFS Depth Level
        #   - tracking min num of moves used to reach current depth level
        moves = 0

        while queue:

            moves += 1

            # Level By Level Expansion:
            #   - drain entire current level before incrementing moves
            #   - guarantees for every state discovered in this pass to
            #     have the same number of moves (depth) from start
            for _ in range(len(queue)):

                # Position and keys previous jump:
                row, col, keys = queue.popleft()

                # Explore Neighbors:
                # apply all 4 cardinal moves from the current state
                for dr, dc in dirs:

                    nr, nc = row + dr, col + dc

                    # Bounds Check:
                    # skip moves that fall off the grid
                    if not (0 <= nr < m and 0 <= nc < n):
                        continue

                    cell = grid[nr][nc]

                    # Wall Pruning:
                    # walls are never passable regardless of keys held
                    if cell == '#':
                        continue

                    nextKeys = keys

                    # Lock Check:
                    # an uppercase cell is only passable if the matching
                    # key bit is already set in the current bitmask
                    if cell.isupper():
                        keyBit = 1 << (ord(cell) - ord('A'))
                        if not (keys & keyBit):
                            continue

                    # Key Pickup:
                    # a lowercase cell updates the bitmask with its bit,
                    # picked up automatically on stepping onto it
                    elif cell.islower():
                        nextKeys = keys | (1 << (ord(cell) - ord('a')))

                    # Check:
                    # if all keys have been collected, we are guaranteed
                    # to have the minimum number of moves
                    if nextKeys == allKeysMask:
                        return moves

                    # Early Pruning:
                    # enque new state (nr, nc, nextKeys) if not already
                    # visited, since revisiting can never yield a
                    # shorter path than the first time it was reached
                    nextState = (nr, nc, nextKeys)
                    if nextState not in visited:
                        visited.add(nextState)
                        queue.append(nextState)

        # All reachable (position, keys) states processed without
        # collecting every key, no path exists that gathers them all

        # overall: tc O(m * n * 2^k), since each of the m*n cells can be
        #   paired with up to 2^k distinct key bitmasks, and every state
        #   is expanded a constant number of times
        # overall: sc O(m * n * 2^k), for the visited set storing every
        #   explored (position, keys bitmask) state
        return -1