[DFS][Python] time beats 100% solutions
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. check the district w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. check the district which would be diffused.\n2. build the wall by the information from 1.\n3. diffusing for current districts.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\ndi = [-1, 0, 1, 0]\ndj = [0, 1, 0, -1]\n\ndef dfs_check(i, j, n, m, dist_no, matrix, dist, visit_dict):\n    visit_dict[(i, j)] = True\n    matrix[i][j] = dist_no\n    for k in range(4):\n        new_i = di[k] + i\n        new_j = dj[k] + j\n        # -1: in the wall\n        if new_i >= 0 and new_i < n and new_j >= 0 and new_j < m and (new_i, new_j) not in visit_dict and matrix[new_i][new_j] != -1:\n            # district is visited and could be diffused\n            if matrix[new_i][new_j] == -dist_no:\n                dist.wall += 1\n            # district is not visited and could be diffused\n            elif matrix[new_i][new_j] <= 0:\n                dist.wall += 1\n                dist.diffusion += 1\n                matrix[new_i][new_j] = -dist_no\n            # connected and diffused district\n            elif matrix[new_i][new_j] > 0:\n                dfs_check(new_i, new_j, n, m, dist_no, matrix, dist, visit_dict)\n\ndef dfs_build_wall(i, j, n, m, dist_no, matrix):\n    matrix[i][j] = -1\n    for k in range(4):\n        new_i = di[k] + i\n        new_j = dj[k] + j\n        if new_i >= 0 and new_i < n and new_j >= 0 and new_j < m:\n            if matrix[new_i][new_j] == -dist_no:\n                flag = False\n                for k1 in range(4):\n                    new_ii = di[k1] + new_i\n                    new_jj = dj[k1] + new_j\n                    if new_ii >= 0 and new_ii < n and new_jj >= 0 and new_jj < m:\n                        if matrix[new_ii][new_jj] > 0 and matrix[new_ii][new_jj] != dist_no:\n                            flag = True\n                if not flag:\n                    matrix[new_i][new_j] = 0\n            if matrix[new_i][new_j] == dist_no:\n                dfs_build_wall(new_i, new_j, n, m, dist_no, matrix)\n\ndef dfs_diffuse(i, j, n, m, dist_no, matrix, visit_dict):\n    visit_dict[(i, j)] = True\n    matrix[i][j] = 1\n    for k in range(4):\n        new_i = di[k] + i\n        new_j = dj[k] + j\n        if new_i >= 0 and new_i < n and new_j >= 0 and new_j < m and (new_i, new_j) not in visit_dict:\n            if matrix[new_i][new_j] == 0 or matrix[new_i][new_j] < -1:\n                matrix[new_i][new_j] = 1\n                visit_dict[(new_i, new_j)] = True\n            elif matrix[new_i][new_j] == dist_no:\n                dfs_diffuse(new_i, new_j, n, m, dist_no, matrix, visit_dict)\n\nclass Dist:\n    def __init__(self, i, j, wall, diffusion):\n        self.i = i\n        self.j = j\n        self.wall = wall\n        self.diffusion = diffusion\n\nclass Solution:\n    def containVirus(self, matrix: List[List[int]]) -> int:\n        n = len(matrix)\n        m = len(matrix[0])\n        total_wall = 0\n        while True:\n            # calculate diffusion\n            dist_no = 2\n            dist_dict = {}\n            max_diffusion = 0\n            max_dist_no = 0\n            visit_dict = {}\n            for i in range(n):\n                for j in range(m):\n                    if matrix[i][j] == 1 or matrix[i][j] >= dist_no:\n                        dist = Dist(i, j, 0, 0)\n                        dfs_check(i, j, n, m, dist_no, matrix, dist, visit_dict)\n                        if dist.diffusion > max_diffusion:\n                            max_diffusion = dist.diffusion\n                            max_dist_no = dist_no\n                        dist_dict[dist_no] = dist\n                        dist_no += 1\n\n            if max_diffusion == 0:\n                break\n\n            # calculate wall\n            total_wall += dist_dict[max_dist_no].wall\n\n            # build wall\n            dfs_build_wall(dist_dict[max_dist_no].i, dist_dict[max_dist_no].j, n, m, max_dist_no, matrix)\n\n            # diffuse\n            del dist_dict[max_dist_no]\n            visit_dict = {}\n            for dist_no, dist in dist_dict.items():\n                dfs_diffuse(dist.i, dist.j, n, m, dist_no, matrix, visit_dict)\n        return total_wall\n```
['Python3']