[Golang] DFS easy to understand
go\nfunc containVirus(isInfected [][]int) int {\n  m, n := len(isInfected), len(isInfected[0])\n  var res int\n  for {\n    // Let\'s do a depth first search an
```go\nfunc containVirus(isInfected [][]int) int {\n  m, n := len(isInfected), len(isInfected[0])\n  var res int\n  for {\n    // Let\'s do a depth first search and find the region that spread the most cells\n    // (i.e) needs more walls to be built\n    visited := make([][]bool, m)\n    for i := 0; i < m; i++ {\n      visited[i] = make([]bool, n)\n    }\n    // We want to focus on the region that can affect the most unaffected neighbors\n    // The unaffected neighbors and the walls needed is different because an unaffected neighbor\n    // can be infected by multiple neighbors and hence will need multiple walls.\n    var wallsNeeded [][4]int // <x, y, uninfectedNeighbors, walls>\n    for i := 0; i < m; i++ {\n      for j := 0; j < n; j++ {\n        if isInfected[i][j] == 1 && !visited[i][j] {\n          visited[i][j] = true\n          uninfectedNeighbors := make(map[[2]int]bool)\n          count := countWalls(isInfected, visited, i, j, uninfectedNeighbors)\n          wallsNeeded = append(wallsNeeded, [4]int{i, j, len(uninfectedNeighbors), count})\n        }\n      }\n    }\n    if len(wallsNeeded) == 0 {\n      break\n    }\n    // Let\'s sort wallsNeeded in descending order on the number of walls\n    sort.Slice(wallsNeeded, func(i, j int) bool {\n      return wallsNeeded[i][2] > wallsNeeded[j][2]\n    })\n    res += wallsNeeded[0][3]\n    buildWall(isInfected, wallsNeeded[0][0], wallsNeeded[0][1])\n    spread(isInfected)\n  }\n  return res\n}\n\nvar directions = [4][2]int{{0, -1}, {-1, 0}, {1, 0}, {0, 1}}\n\nfunc countWalls(isInfected [][]int, visited [][]bool, row, col int, uninfectedNeighbors map[[2]int]bool) int {\n  m, n := len(isInfected), len(isInfected[0])\n  var walls int\n  for _, dir := range directions {\n    x, y := row + dir[0], col + dir[1]\n    if x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] {\n      if isInfected[x][y] == 0 {\n        uninfectedNeighbors[[2]int{x, y}] = true\n        walls++\n      } else if isInfected[x][y] == 1 {\n        visited[x][y] = true\n        walls += countWalls(isInfected, visited, x, y, uninfectedNeighbors)\n      }\n    }\n  }\n  return walls\n}\n\n// buildWall builds the wall around the given region (specified by a single cell)\n// It uses DFS and marks the cells with -1 which means the region is contained\nfunc buildWall(isInfected [][]int, row, col int) {\n  m, n := len(isInfected), len(isInfected[0])\n  isInfected[row][col] = -1\n  for _, dir := range directions {\n    x, y := row+dir[0], col+dir[1]\n    if x >= 0 && x < m && y >= 0 && y < n && isInfected[x][y] == 1 {\n      buildWall(isInfected, x, y)\n    }\n  }\n}\n\n// spread spreads the virus from the infected positions to their neighbor cells\nfunc spread(isInfected [][]int) {\n  m, n := len(isInfected), len(isInfected[0])\n  for i := 0; i < m; i++ {\n    for j := 0; j < n; j++ {\n      if isInfected[i][j] == 1 {\n        for _, dir := range directions {\n          x, y := i+dir[0], j+dir[1]\n          if x >= 0 && x < m && y >= 0 && y < n && isInfected[x][y] == 0 {\n            // newly infected cells with special character since we don\'t want the neighbor\n            // of this cell to be infected\n            isInfected[x][y] = 2 \n          }\n        }\n      }\n    }\n  }\n  // Remove the special marking\n  for i := 0; i < m; i++ {\n    for j := 0; j < n; j++ {\n      if isInfected[i][j] == 2 {\n        isInfected[i][j] = 1\n      }\n    }\n  }\n}\n```
['Go']