some interesting graph problem

2 min read

Shortest Bridge

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.) Now, we may change 0s to 1s so as to connect the two islands together to form 1 island. Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example Example 1: Input：[[0,1],[1,0]] Output：1 Explanation：Flip 0 on (0,0) or (1,1) Example 2: Input：[[0,1,0],[0,0,0],[0,0,1]] Output：2 Explanation：Flip 0 on (0,2) and (1,2)

Notice 1 <= A.length = A[0].length <= 100 A[i][j] == 0 or A[i][j] == 1

class Solution:
    def ShortestBridge(self, A):
        def dfs(i, j):
            A[i][j] = -1
            bfs.append((i, j))
            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                if 0 <= x < n and 0 <= y < n and A[x][y] == 1:
                    dfs(x, y)
        def first():
            for i in range(n):
                for j in range(n):
                    if A[i][j]:
                        return i, j
        n, step, bfs = len(A), 0, []
        dfs(*first())
        while bfs:
            new = []
            for i, j in bfs:
                for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                    if 0 <= x < n and 0 <= y < n:
                        if A[x][y] == 1:
                            return step
                        elif not A[x][y]:
                            A[x][y] = -1
                            new.append((x, y))
            step += 1
            bfs = new

Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0. Example Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = [ [“a”, “b”], [“b”, “c”] ], values = [2.0, 3.0], queries = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].

class Solution:
    """
    @param equations: 
    @param values: 
    @param queries: 
    @return: return a double type array
    """
    def calcEquation(self, equations, values, queries):
        # write your code here
        
        def dfs(s,e,visited):
            visited.add(s)
            if s not in graph:
                return -1.0
            if s == e:
                return 1.0
            for node,value in graph[s]:
                if node in visited:
                    continue
                if node == e:
                    return value
                found = dfs(node,e,visited)
                if found != -1.0:
                    return value*found
            return -1.0
                
        
        import collections
        
        graph = collections.defaultdict(list)
        
        for (s,e),value in zip(equations,values):
            graph[s].append((e,value))
            graph[e].append((s,1.0/value))
        return [dfs(s,e,set()) for s,e in queries]