Graph or search problems: each state is a node and all edges (connections) have uniform (or none) weights.
Need to consider which state need to add to the queue (the Matrix 01 problem).
Template
def bfs(...): # handle edge case, early returns # most of the time it is the seed value pushed to the queue # Init queue = Deque() visited = ... """ Add a new item to the queue. Additional step includes checking whether the item is already visited. """ def add_to_queue(new_item): ... """ Find all valid neighbors given the current item and add them to the queue. Optimization: early termination by checking the stop condition on the neighbor """ def neighbors(item): ... def update_queue(item): for neighbor in neighbors(item): add_to_queue(neighbor) queue.append(seed) stop_condition = False while stop_condition and len(queue) > 0: for _ in range(len(queue)): cur_item = queue.popleft() if check(value): stop_condition = True break update_queue(cur_item)