题解 | #模拟战役#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	"sort"
	"strings"
)

type E struct {
	x, y int
}

type UnionSet struct {
	eMap     map[E]bool
	faterMap map[E]E
	rankMap  map[E]int
}

func NewUnionSet() *UnionSet {
	return &UnionSet{
		make(map[E]bool),
		make(map[E]E),
		make(map[E]int),
	}
}

func (us *UnionSet) getHead(e E) E {
	if us.faterMap[e] == e {
		return e
	}
	head := us.getHead(us.faterMap[e])
	us.faterMap[e] = head
	return head
}
func (us *UnionSet) isSame(var1, var2 E) bool {
	return us.getHead(var1) == us.getHead(var2)
}
func (us *UnionSet) union(var1, var2 E) {
	if us.isSame(var1, var2) {
		return
	}
	fvar1, fvar2 := us.faterMap[var1], us.faterMap[var2]
	if us.rankMap[fvar1] >= us.rankMap[fvar2] {
		us.faterMap[fvar2] = fvar1
		us.rankMap[fvar1] += us.rankMap[fvar2]
		delete(us.rankMap, fvar2)
	} else {
		us.faterMap[fvar1] = fvar2
		us.rankMap[fvar2] += us.rankMap[fvar1]
		delete(us.rankMap, fvar1)
	}

}

// 8方向
var d = [8][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}}

func merge(uset *UnionSet) {
	for key, _ := range uset.eMap {
		for i := 0; i < 8; i++ {
			if _, ok := uset.eMap[E{key.x + d[i][0], key.y + d[i][1]}]; ok {
				uset.union(key, E{key.x + d[i][0], key.y + d[i][1]})
			}
		}
	}
}

func NC14698(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var m int
	Fscan(in, &m)
	SiJi := [4][]string{}
	sijiUset := NewUnionSet()
	for i := 0; i < 4; i++ {
		var line string
		Fscan(in, &line)
		SiJi[i] = strings.Split(line, "")
		for j := 0; j < m; j++ {
			if SiJi[i][j] == "*" {
				e := E{i, j}
				sijiUset.eMap[e] = true
				sijiUset.faterMap[e] = e
				sijiUset.rankMap[e] = 1
			}
		}
	}

	QiQi := [4][]string{}
	qiqiUset := NewUnionSet()
	for i := 0; i < 4; i++ {
		var line string
		Fscan(in, &line)
		QiQi[i] = strings.Split(line, "")
		for j := 0; j < m; j++ {
			if QiQi[i][j] == "*" {
				e := E{i, j}
				qiqiUset.eMap[e] = true
				qiqiUset.faterMap[e] = e
				qiqiUset.rankMap[e] = 1
			}
		}
	}
	merge(sijiUset)
	merge(qiqiUset)

	if len(qiqiUset.rankMap) < len(sijiUset.rankMap) {
		Fprintln(out, -1)
	} else {
		a := make([]int, len(qiqiUset.rankMap))
		k := 0

		total := 0
		for _, v := range qiqiUset.rankMap {
			a[k] = v
			total += v
			k++
		}
		sort.Ints(a)

		tmp := 0
		for i := 0; i < len(sijiUset.rankMap)-1; i++ {
			tmp += a[i]
		}
		Fprintln(out, total-tmp)
	}
}

func main() {
	NC14698(os.Stdin, os.Stdout)
}