2022-05-17：在一个地图上有若干个炸弹，每个炸弹会呈现十字型引爆。每个炸弹都有其当量值，这个值决定了这个炸弹的爆炸半径。

package main

import (
  "fmt"
  "sort"
)

func main() {
  map0 := [][]int{
    {0, 0, 2, 0, 2},
    {1, 0, 0, 0, 0},
    {0, 0, 1, 0, 2},
    {0, 0, 1, 0, 0},
    {0, 0, 1, 0, 0},
  }
  ans := minBombs2(map0)
  fmt.Println(ans)
}

// 正式方法
// 用到有序表 + 强连通分量
func minBombs2(map0 [][]int) int {
  n := len(map0)
  rowTreeMaps := make([]map[int]int, 0)
  rowTreeMapsi := make([][]int, 0)
  colTreeMaps := make([]map[int]int, 0)
  colTreeMapsi := make([][]int, 0)
  for i := 0; i < n; i++ {
    rowTreeMaps = append(rowTreeMaps, make(map[int]int))
    rowTreeMapsi = append(rowTreeMapsi, make([]int, 0))
    colTreeMaps = append(colTreeMaps, make(map[int]int))
    colTreeMapsi = append(colTreeMapsi, make([]int, 0))
  }
  m := 0
  for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
      if map0[i][j] != 0 {
        m++
        rowTreeMaps[i][j] = m
        rowTreeMapsi[i] = append(rowTreeMapsi[i], j)
        colTreeMaps[j][i] = m
        colTreeMapsi[j] = append(colTreeMapsi[j], i)
      }
    }
  }
  for i := 0; i < n; i++ {
    sort.Ints(rowTreeMapsi[i])
    sort.Ints(colTreeMapsi[i])
  }
  edges := make([][]int, 0)
  for i := 0; i <= m; i++ {
    edges = append(edges, make([]int, 0))
  }
  for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
      if map0[i][j] != 0 {
        rowTreeMap := rowTreeMaps[i]
        rowTreeMapi := rowTreeMapsi[i]
        colTreeMap := colTreeMaps[j]
        colTreeMapi := colTreeMapsi[j]
        from := rowTreeMap[j]
        col := j - 1
        for floorKey(rowTreeMapi, col) != -1 && j-rowTreeMapi[floorKey(rowTreeMapi, col)] <= map0[i][j] {
          col = rowTreeMapi[floorKey(rowTreeMapi, col)]
          edges[from] = append(edges[from], rowTreeMap[col])
          col--
        }
        col = j + 1
        for ceilingKey(rowTreeMapi, col) != -1 && rowTreeMapi[ceilingKey(rowTreeMapi, col)]-j <= map0[i][j] {
          col = rowTreeMapi[ceilingKey(rowTreeMapi, col)]
          edges[from] = append(edges[from], rowTreeMap[col])
          col++
        }
        row := i - 1
        for floorKey(colTreeMapi, row) != -1 && i-colTreeMapi[floorKey(colTreeMapi, row)] <= map0[i][j] {
          row = colTreeMapi[floorKey(colTreeMapi, row)]
          edges[from] = append(edges[from], colTreeMap[row])
          row--
        }
        row = i + 1
        for ceilingKey(colTreeMapi, row) != -1 && colTreeMapi[ceilingKey(colTreeMapi, row)]-i <= map0[i][j] {
          row = colTreeMapi[ceilingKey(colTreeMapi, row)]
          edges[from] = append(edges[from], colTreeMap[row])
          row++
        }
      }
    }
  }
  scc := NewStronglyConnectedComponents(edges)
  sccn := scc.getSccn()
  in := make([]int, sccn+1)
  out := make([]int, sccn+1)
  dag := scc.getShortGraph()
  for i := 1; i <= sccn; i++ {
    for _, j := range dag[i] {
      out[i]++
      in[j]++
    }
  }
  zeroIn := 0
  for i := 1; i <= sccn; i++ {
    if in[i] == 0 {
      zeroIn++
    }
  }
  return zeroIn
}

// 在arr上，找满足>=value的最左位置
func ceilingKey(arr []int, v int) int {
  L := 0
  R := len(arr) - 1
  index := -1 // 记录最左的对号
  for L <= R {
    mid := L + (R-L)>>1
    if arr[mid] >= v {
      index = mid
      R = mid - 1
    } else {
      L = mid + 1
    }
  }
  return index
}

// 在arr上，找满足<=value的最右位置
func floorKey(arr []int, v int) int {
  L := 0
  R := len(arr) - 1
  index := -1 // 记录最右的对号
  for L <= R {
    mid := L + (R-L)>>1
    if arr[mid] <= v {
      index = mid
      L = mid + 1
    } else {
      R = mid - 1
    }
  }
  return index
}

type StronglyConnectedComponents struct {
  nexts     [][]int
  n         int
  stack     []int
  stackSize int
  dfn       []int
  low       []int
  cnt       int
  scc       []int
  sccn      int
}

// 请保证点的编号从1开始，不从0开始
// 注意：
// 如果edges里有0、1、2...n这些点，那么容器edges的大小为n+1
// 但是0点是弃而不用的，所以1..n才是有效的点，所以有效大小是n
func NewStronglyConnectedComponents(edges [][]int) *StronglyConnectedComponents {
  ans := &StronglyConnectedComponents{}
  ans.nexts = edges
  ans.init()
  ans.scc0()
  return ans
}

func (this *StronglyConnectedComponents) init() {
  this.n = len(this.nexts)
  this.stack = make([]int, this.n)
  this.stackSize = 0
  this.dfn = make([]int, this.n)
  this.low = make([]int, this.n)
  this.cnt = 0
  this.scc = make([]int, this.n)
  this.sccn = 0
  this.n--
}

func (this *StronglyConnectedComponents) scc0() {
  for i := 1; i <= this.n; i++ {
    if this.dfn[i] == 0 {
      this.tarjan(i)
    }
  }
}

func (this *StronglyConnectedComponents) tarjan(p int) {
  this.cnt++
  this.dfn[p] = this.cnt
  this.low[p] = this.cnt
  this.stack[this.stackSize] = p
  this.stackSize++
  for _, q := range this.nexts[p] {
    if this.dfn[q] == 0 {
      this.tarjan(q)
    }
    if this.scc[q] == 0 {
      if this.low[p] > this.low[q] {
        this.low[p] = this.low[q]
      }
    }
  }
  if this.low[p] == this.dfn[p] {
    this.sccn++
    top := 0
    for {
      this.stackSize--
      top = this.stack[this.stackSize]
      this.scc[top] = this.sccn
      if top == p {
        break
      }
    }
  }
}

func (this *StronglyConnectedComponents) getScc() []int {
  return this.scc
}

func (this *StronglyConnectedComponents) getSccn() int {
  return this.sccn
}

func (this *StronglyConnectedComponents) getShortGraph() [][]int {
  shortGraph := make([][]int, 0)
  for i := 0; i <= this.sccn; i++ {
    shortGraph = append(shortGraph, make([]int, 0))
  }
  for u := 1; u <= this.n; u++ {
    for _, v := range this.nexts[u] {
      if this.scc[u] != this.scc[v] {
        shortGraph[this.scc[u]] = append(shortGraph[this.scc[u]], this.scc[v])
      }
    }
  }
  return shortGraph
}