1.水流问题
使用两个visited数组即可。
1.1 DFS版
package main
import "fmt"
var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
func main() {
var M, N int
fmt.Scanln(&N, &M)
sea := make([][]int, N)
one_visited := make([][]bool, N)
two_visited := make([][]bool, N)
for i := 0; i < N; i++ {
sea[i] = make([]int, M)
one_visited[i] = make([]bool, M)
two_visited[i] = make([]bool, M)
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
fmt.Scan(&sea[i][j])
}
}
for i := 0; i < N; i++ {
dfs(i, 0, N, M, &sea, &one_visited)
dfs(i, M-1, N, M, &sea, &two_visited)
}
for j := 0; j < M; j++ {
dfs(0, j, N, M, &sea, &one_visited)
dfs(N-1, j, N, M, &sea, &two_visited)
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
if one_visited[i][j] && two_visited[i][j] {
fmt.Printf("%d %d\n", i, j)
}
}
}
}
func dfs(x, y, N, M int, sea *[][]int, visited *[][]bool) {
if (*visited)[x][y] {
return
}
(*visited)[x][y] = true
for i := 0; i < 4; i++ {
newX := x + direction[i][0]
newY := y + direction[i][1]
if newX < 0 || newX >= N || newY < 0 || newY >= M {
continue
}
if (*sea)[newX][newY] > (*sea)[x][y] && !(*visited)[newX][newY] {
dfs(newX, newY, N, M, sea, visited)
}
}
}
1.2 BFS版
package main
import "fmt"
var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
func main() {
var M, N int
fmt.Scanln(&N, &M)
sea := make([][]int, N)
one_visited := make([][]bool, N)
two_visited := make([][]bool, N)
for i := 0; i < N; i++ {
sea[i] = make([]int, M)
one_visited[i] = make([]bool, M)
two_visited[i] = make([]bool, M)
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
fmt.Scan(&sea[i][j])
}
}
for i := 0; i < N; i++ {
bfs(i, 0, N, M, &sea, &one_visited)
bfs(i, M-1, N, M, &sea, &two_visited)
}
for j := 0; j < M; j++ {
bfs(0, j, N, M, &sea, &one_visited)
bfs(N-1, j, N, M, &sea, &two_visited)
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
if one_visited[i][j] && two_visited[i][j] {
fmt.Printf("%d %d\n", i, j)
}
}
}
}
func bfs(x, y, N, M int, sea *[][]int, visited *[][]bool) int {
if (*visited)[x][y] {
return 0
}
queue := make([][2]int, 0)
queue = append(queue, [2]int{x, y})
(*visited)[x][y] = true
area := 0
for len(queue) != 0 {
pos := queue[0]
queue = queue[1:]
area += 1
for i := 0; i < 4; i++ {
newX := pos[0] + direction[i][0]
newY := pos[1] + direction[i][1]
if newX < 0 || newX >= N || newY < 0 || newY >= M {
continue
}
if (*sea)[newX][newY] > (*sea)[pos[0]][pos[1]] && !(*visited)[newX][newY] {
queue = append(queue, [2]int{newX, newY})
(*visited)[newX][newY] = true
}
}
}
return area
}
2.建造最大岛屿
package main
import "fmt"
var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
var M, N int
func main() {
fmt.Scanln(&N, &M)
sea := make([][]int, N)
visited := make([][]bool, N)
island := make(map[int]int, 0)
for i := 0; i < N; i++ {
sea[i] = make([]int, M)
visited[i] = make([]bool, M)
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
fmt.Scan(&sea[i][j])
}
}
isLandIndex := 1
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
if sea[i][j] == 1 && !visited[i][j] {
area := 0
dfs(i, j, isLandIndex, &sea, &visited, &area)
island[isLandIndex] = area
isLandIndex += 1
}
}
}
maxArea := 1
for _, area := range island {
if area > maxArea {
maxArea = area
}
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
if sea[i][j] == 0 {
//尝试在这里建造小岛
area := 1
connIsland := make([]int, 0)
for k := 0; k < 4; k++ {
newX := i + direction[k][0]
newY := j + direction[k][1]
if newX < 0 || newX >= N || newY < 0 || newY >= M {
continue
}
if sea[newX][newY] != 0 && !isInList(sea[newX][newY], connIsland) {
area += island[sea[newX][newY]]
connIsland = append(connIsland, sea[newX][newY])
}
}
if area > maxArea {
maxArea = area
}
}
}
}
//for key, value := range island {
// fmt.Printf("小岛编号：%d,小岛面积：%d \n", key, value)
//}
fmt.Println(maxArea)
}
func isInList(isLandIndex int, isLands []int) bool {
for i := 0; i < len(isLands); i++ {
if isLandIndex == isLands[i] {
return true
}
}
return false
}
func dfs(x, y, seaIndex int, sea *[][]int, visited *[][]bool, area *int) {
(*visited)[x][y] = true
(*sea)[x][y] = seaIndex
*area = (*area) + 1
for i := 0; i < 4; i++ {
newX := x + direction[i][0]
newY := y + direction[i][1]
if newX < 0 || newX >= N || newY < 0 || newY >= M {
continue
}
if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
dfs(newX, newY, seaIndex, sea, visited, area)
}
}
}
3.字符串接龙
package main
import "fmt"
var N int
var beginStr, endStr string
func main() {
fmt.Scanln(&N)
fmt.Scanf("%s %s", &beginStr, &endStr)
strList := make([]string, 0)
strMap := make(map[string]int)
strMap[beginStr] = 0
strMap[endStr] = 1
strList = append(strList, beginStr)
strList = append(strList, endStr)
strIndex := 2
for i := 0; i < N; i++ {
var tempStr string
fmt.Scanln(&tempStr)
strMap[tempStr] = strIndex
strList = append(strList, tempStr)
strIndex++
}
if beginStr == endStr {
fmt.Println(0)
return
}
m := make([][]int, N+2)
for i := 0; i < N+2; i++ {
m[i] = make([]int, N+2)
}
for i := 0; i < N+2; i++ {
for j := i; j < N+2; j++ {
if canTransfer(strList[i], strList[j]) {
m[i][j] = 1
m[j][i] = 1
}
}
}
//printMatrix(m)
// 开启bfs
step := bfs(0, 1, &m)
fmt.Println(step)
}
func canTransfer(str1, str2 string) bool {
diff := 0
for i := 0; i < len(str1); i++ {
if str1[i] != str2[i] {
diff++
}
}
return diff == 1
}
func bfs(beginIndex, endIndex int, m *[][]int) int {
queue := make([]int, 0)
tempQueue := make([]int, 0)
queue = append(queue, beginIndex)
strSet := make(map[int]struct{})
strSet[beginIndex] = struct{}{}
step := 1
for len(queue) != 0 {
nowIndex := queue[0]
if nowIndex == endIndex {
return step
}
queue = queue[1:]
for i := 0; i < N+2; i++ {
_, ok := strSet[i]
if ok {
continue
}
if (*m)[nowIndex][i] == 1 {
tempQueue = append(tempQueue, i)
//表示已经在队列中
strSet[i] = struct{}{}
}
}
if len(queue) == 0 {
for i := 0; i < len(tempQueue); i++ {
queue = append(queue, tempQueue[i])
}
tempQueue = make([]int, 0)
step++
}
}
return 0
}
4.有向图的完全可达性
package main
import "fmt"
var directions = [4][2]int{
{0, 1},
{0, -1},
{1, 0},
{-1, 0},
}
var N, M int
func main() {
fmt.Scanln(&N, &M)
m := make([][]int, N+1)
visited := make([]bool, N+1)
for i := 0; i < N+1; i++ {
m[i] = make([]int, N+1)
}
for i := 0; i < M; i++ {
var start, end int
fmt.Scanln(&start, &end)
m[start][end] = 1
}
//bfs
reachCount := bfs(1, &visited, &m)
if reachCount == N {
fmt.Println(1)
} else {
fmt.Println(-1)
}
}
func bfs(start int, visited *[]bool, m *[][]int) int {
queue := make([]int, 0)
queue = append(queue, start)
(*visited)[start] = true
reachCount := 1
for len(queue) != 0 {
now := queue[0]
queue = queue[1:]
for i := 1; i < N+1; i++ {
if !(*visited)[i] && (*m)[now][i] == 1 {
queue = append(queue, i)
(*visited)[i] = true
reachCount++
}
}
}
return reachCount
}
5.岛屿的周长
package main
import "fmt"
var directions = [4][2]int{
{0, 1},
{0, -1},
{1, 0},
{-1, 0},
}
var N, M int
func main() {
fmt.Scanln(&N, &M)
m := make([][]int, N)
for i := 0; i < N; i++ {
m[i] = make([]int, M)
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
fmt.Scan(&m[i][j])
}
}
//遍历map并向四方探索
result := 0
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
if m[i][j] == 1 {
result += getEdgeNum(i, j, &m)
}
}
}
fmt.Println(result)
}
func getEdgeNum(x, y int, m *[][]int) int {
edge := 4
for i := 0; i < 4; i++ {
newX := x + directions[i][0]
newY := y + directions[i][1]
if newX < 0 || newX >= N || newY < 0 || newY >= M{
continue
}
if (*m)[newX][newY] == 1{
edge--
}
}
return edge
}