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

2022-05-17：在一个地图上有若干个炸弹，每个炸弹会呈现十字型引爆。 每个炸弹都有其当量值，这个值决定了这个炸弹的爆炸半径。 如果一个炸弹被引爆时，有其它炸弹在其爆炸半径内，那么其它炸弹也会爆炸。 请问使地图上所有炸弹爆炸所需的最少人为引爆次数。 例如： 0,0,0,0,0 0,0,0,1,0 0,0,0,0,0 上图中val为1的单元是一个炸弹，人为引爆后地图变成下面的样子： 0, 0, 0,-1, 0 0, 0,-1,-1,-1 0, 0, 0,-1, 0 题目并没有给数据量，面经题目的通病。 来自亚马逊。

答案2022-05-17：

并查集不对。 贪心最大当量不对。 贪心最多不对。 有序表 + 强连通分量。

代码用golang编写。代码如下：

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
}

执行结果如下：

左神java代码