# CSPT27 Lecture 14
## All Paths from Source to Target

from collections import deque, defaultdict
class Solution:
    """
    1. Translate the problem into graph terminology
    vertices - each index in the list aka graph[i]
    edges - graph[i][j] aka each sublist is that node's neighbors
    2. build your graph
    We don't need to build out a graph, we can just traverse the graph
    that's given to us
    3. Traverse the graph
    We need to do a search for the path to the last node
    Type of search doesn't matter (DFS/BFS)
    """
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        self.allPathsSourceTargetHelper(graph, 0, len(graph) - 1, [0], res)
        return res
        
    def allPathsSourceTargetHelper(self, graph, currNode, destinationNode, currPath, res):
        if currNode == destinationNode:
            res.append(currPath)
        else:
            for neighbor in graph[currNode]:
                newPath = currPath.copy()
                newPath.append(neighbor)
                self.allPathsSourceTargetHelper(graph, neighbor, destinationNode, newPath, res)

    def bfsAllPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        destinationNode = len(graph) - 1
        queue = deque()
        queue.append((0, [0]))
        res = []
        while len(queue) > 0:
            curr = queue.popleft()
            currNode, currPath = curr[0], curr[1]
            if currNode == destinationNode:
                res.append(currPath)
            else:
                for neighbor in graph[currNode]:
                    newPath = currPath.copy()
                    newPath.append(neighbor)
                    queue.append((neighbor, newPath))
        return res
    
    def dfsAllPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        destinationNode = len(graph) - 1
        stack = deque()
        stack.append((0, [0]))
        res = []
        while len(stack) > 0:
            curr = stack.pop()
            currNode, currPath = curr[0], curr[1]
            if currNode == destinationNode:
                res.append(currPath)
            else:
                for neighbor in graph[currNode]:
                    newPath = currPath.copy()
                    newPath.append(neighbor)
                    stack.append((neighbor, newPath))
        return res

## Flood-fill

from collections import deque
class Solution:
    """
    Plan
    1. Translate the problem into graph terminology
    Not exactly a graph, but we can treat a  matrix very similar to a graph where a node
    will be an element in the matrix. And its neighbors will be the ones right next to it.
    
    2. Build your graph
    Just traverse the matrix/image that's given to you
    
    3. Traverse the graph
    Use a stack/queue to push neighboring pixels and keep traversing the image
    Change the pixels value if its the value you want to change
    Ignore pixels which have a different value
    """
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        colorToChange = image[sr][sc]
        queue = deque()
        queue.append((sr, sc))
        visited = set()
        numRows, numCols = len(image), len(image[0])
        while len(queue) > 0:
            currPoint = queue.popleft()
            currRow, currColumn = currPoint[0], currPoint[1]
            if currPoint in visited:
                continue
            if currRow < 0 or currRow >= numRows or currColumn < 0 or currColumn >= numCols:
                continue
            if image[currRow][currColumn] != colorToChange:
                continue
            visited.add(currPoint)
            image[currRow][currColumn] = newColor
            queue.append((currRow + 1, currColumn))
            queue.append((currRow - 1, currColumn))
            queue.append((currRow, currColumn - 1))
            queue.append((currRow, currColumn + 1))
        return image

## Find Eventual Safe States

from collections import defaultdict

class Solution:
    UNVISITED = 0
    VISITING = 1
    SAFE = 3
    UNSAFE = 4

def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
    numNodes = len(graph)
    state = [Solution.UNVISITED] * numNodes
    for node in range(numNodes):
        if state[node] == Solution.UNVISITED:
            self.dfs(graph, node, state)
    return [node for (node, nodeState) in enumerate(state) if nodeState == Solution.SAFE]

def dfs(self, graph, currNode, state):
    if state[currNode] == Solution.SAFE:
        return True
    if state[currNode] == Solution.VISITING or state[currNode] == Solution.UNSAFE:
        return False
    state[currNode] = Solution.VISITING
    isSafe = True
    for neighbor in graph[currNode]:
        isSafe &= self.dfs(graph, neighbor, state)
        if not isSafe:
            break
    state[currNode] = Solution.SAFE if isSafe else Solution.UNSAFE
    return isSafe