<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 BFS in Graph
Graph Valid Tree
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. 
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
http
Step1:  Clone Graph
http
Step2:  Search Graph Nodes
Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can't find.
There is a mapping store the nodes' values in the given parameters.
Notice
It's guaranteed there is only one available solution
http
Step4:  Topological Sorting
Given an directed graph, a topological order of the graph nodes is defined as follow
Step6:  BFS in Matrix
Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1
Step7:  Zombie in Matrix
Given a 2D grid, each cell is either a wall 2, a zombie 1 or people 0 (the number zero, one, two).Zombies can turn the nearest people(up/down/left/right) into zombies every day, but can not through wall. How long will it take to turn all people into zombies? Return -1 if can not turn all people into zombies.
Example
Given a matrix
Step8:  Knight Shortest Path
http
<ASSISTANT_TASK:>
Python Code:
class Solution:
    # @param {int} n an integer
    # @param {int[][]} edges a list of undirected edges
    # @return {boolean} true if it's a valid tree, or false
    def validTree(self, n, edges):
        # Write your code here
        dic = {i: [] for i in range(n)}
        for i, j in edges:
            dic[i].append(j)
            dic[j].append(i)
        visited = [0 for i in range(n)]
        layer, visited[0] = [0], 1
        while layer:
            next_layer = []
            for node in layer:
                for next_node in dic[node]:
                    if visited[next_node]:
                        return False
                    dic[next_node].remove(node)
                    next_layer.append(next_node)
                    visited[next_node] = 1
            layer = next_layer
        
        return True if sum(visited) == n else False
Explanation: BFS in Graph
Graph Valid Tree
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. 
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
http://www.lintcode.com/en/problem/graph-valid-tree/
https://leetcode.com/problems/graph-valid-tree/#/description
End of explanation
# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def __init__(self):
        self.dict = {}
        
    def cloneGraph(self, node):
        # write your code here
        if node is None:
            return 
        
        nodeCopy = UndirectedGraphNode(node.label)
        self.dict[node] = nodeCopy
        
        queue = [node]
        while queue:
            node = queue.pop(0)
            for n in node.neighbors:
                if n not in self.dict:
                    nc = UndirectedGraphNode(n.label)
                    self.dict[n] = nc
                    self.dict[node].neighbors.append(nc)
                    queue.append(n)
                else:
                    self.dict[node].neighbors.append(self.dict[n])
        
        return nodeCopy
Explanation: Clone Graph
http://www.lintcode.com/en/problem/clone-graph/
https://leetcode.com/problems/clone-graph/#/description
End of explanation
# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
class Solution:
    # @param {UndirectedGraphNode[]} graph a list of undirected graph node
    # @param {dict} values a dict, <UndirectedGraphNode, (int)value>
    # @param {UndirectedGraphNode} node an Undirected graph node
    # @param {int} target an integer
    # @return {UndirectedGraphNode} a node
    def searchNode(self, graph, values, node, target):
        # Write your code here
        if not node:
            return None
        
        if values[node] == target:
            return node
            
        queue = [node]
        visited = set([node])
        while queue:
            node = queue.pop(0)
            for n in node.neighbors:
                if values[n] == target:
                    return n
                if n not in visited:
                    visited.add(n)
                    queue.append(n)
        
        return None
                
Explanation: Search Graph Nodes
Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can't find.
There is a mapping store the nodes' values in the given parameters.
Notice
It's guaranteed there is only one available solution
http://www.lintcode.com/en/problem/search-graph-nodes/
End of explanation
# Definition for a Directed graph node
# class DirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
class Solution:
    
    @param graph: A list of Directed graph node
    @return: A list of graph nodes in topological order.
    
    def topSort(self, graph):
        # write your code here
        dic = {}
        for node in graph:
            dic[node] = 0
        
        for node in graph:
            for n in node.neighbors:
                dic[n] += 1
        
        order = []
        for node in graph:
            if dic[node] == 0:
                order.append(node)
        
        queue = order[:]   ## right way to copy a list!!!
        while queue:
            node = queue.pop(0)
            for n in node.neighbors:
                dic[n] -= 1
                if dic[n] == 0:
                    order.append(n)
                    queue.append(n)
        
        return order if len(order) == len(dic) else None
            
Explanation: Topological Sorting
Given an directed graph, a topological order of the graph nodes is defined as follow:
For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.
http://www.lintcode.com/en/problem/topological-sorting/
End of explanation
class Solution(object):
    def numIslands(self, grid):
        
        :type grid: List[List[str]]
        :rtype: int
        
        if grid is None or len(grid) == 0 or len(grid[0]) == 0:
            return 0
        
        m, n = len(grid), len(grid[0])
        visited = [[False for i in range(n)] for j in range(m)]
        count = 0
        
        def bfs(grid, m, n, x, y):
            dx = [0, 0, 1, -1]
            dy = [1, -1, 0, 0]
            
            queue = [[x, y]]
            visited[x][y] = True
            while queue:
                x, y = queue.pop(0)
                for i in range(4):
                    xx, yy = x + dx[i], y + dy[i]
                    if 0 <= xx < m and 0 <= yy < n:
                        if not visited[xx][yy] and grid[xx][yy] == '1':
                            queue.append([xx, yy])
                        visited[xx][yy] = True
        
        for x in range(m):
            for y in range(n):
                if not visited[x][y] and grid[x][y] == '1':
                    count += 1
                    bfs(grid, m, n, x, y)
        
        return count
        
class Solution:
    # @param {boolean[][]} grid a boolean 2D matrix
    # @return {int} an integer
    def numIslands(self, grid):
        # Write your code here
        if grid is None or len(grid) == 0 or len(grid[0]) == 0:
            return 0
            
        m, n = len(grid), len(grid[0])
        visited = [[False for y in range(n)] for x in range(m)]
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        count = 0
        
        def bfs(x, y):
            queue = [[x, y]]
            while queue:
                x, y = queue.pop(0)
                visited[x][y] = True
                for i in range(4):
                    xx, yy = x + dx[i], y + dy[i]
                    if 0 <= xx < m and 0 <= yy < n:
                        if not visited[xx][yy] and grid[xx][yy] == 1:
                            queue.append([xx, yy])
                        visited[xx][yy] = True
                        
        for x in range(m):
            for y in range(n):
                if not visited[x][y] and grid[x][y] == 1:
                    count += 1
                    bfs(x, y)
        
        return count
Explanation: BFS in Matrix
Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
https://leetcode.com/problems/number-of-islands/#/description
http://www.lintcode.com/en/problem/number-of-islands/
End of explanation
class Solution:
    # @param {int[][]} grid  a 2D integer grid
    # @return {int} an integer
    def zombie(self, grid):
        # Write your code here
        if grid is None or len(grid) == 0 or len(grid[0]) == 0:
            return -1
        
        m, n = len(grid), len(grid[0])
        day, people, zombies = -1, 0, []
        di = [0, 0, 1, -1]
        dj = [1, -1, 0, 0]
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    people += 1
                elif grid[i][j] == 1:
                    zombies.append([i, j])
        
        while zombies:
            new_zombies = []
            for i, j in zombies:
                for k in range(4):
                    zi, zj = i + di[k], j + dj[k]
                    if 0 <= zi < m and 0 <= zj < n and grid[zi][zj] == 0:
                        new_zombies.append([zi, zj])
                        grid[zi][zj] = 1
                        people -= 1
            day += 1
            zombies = new_zombies
            # print day, zombies
        
        return -1 if people > 0 else day
                        
Explanation: Zombie in Matrix
Given a 2D grid, each cell is either a wall 2, a zombie 1 or people 0 (the number zero, one, two).Zombies can turn the nearest people(up/down/left/right) into zombies every day, but can not through wall. How long will it take to turn all people into zombies? Return -1 if can not turn all people into zombies.
Example
Given a matrix:
0 1 2 0 0
1 0 0 2 1
0 1 0 0 0
return 2
http://www.lintcode.com/en/problem/zombie-in-matrix/
End of explanation
# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
class Solution:
    # @param {boolean[][]} grid a chessboard included 0 (False) and 1 (True)
    # @param {Point} source a point
    # @param {Point} destination a point
    # @return {int} the shortest path 
    def shortestPath(self, grid, source, destination):
        # Write your code here
        if grid is None or len(grid) == 0 or len(grid[0]) == 0:
            return -1
        
        m, n = len(grid), len(grid[0])
        d = [(1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1)]
        
        path, step = [[source.x, source.y]], -1
        while path:
            step += 1
            new_path = []
            for x, y in path:
                if [x, y] == [destination.x, destination.y]:
                    return step
                for dx, dy in d:
                    xx, yy = x + dx, y + dy
                    if 0 <= xx < m and 0 <= yy < n and grid[xx][yy] != 1:
                        new_path.append([xx, yy])
                        grid[xx][yy] = 1
            path = new_path
        
        return -1
Explanation: Knight Shortest Path
http://www.lintcode.com/en/problem/knight-shortest-path/
End of explanation
<END_TASK>