岛屿最大的孤岛面积
package main
import "fmt"
var dirPath = [4][2]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}}
var visited [][]bool
var flag bool
var res int
func main() {
var x, y int
fmt.Scanf("%d %d", &x, &y)
// x 行y 列初始化临界矩阵
var graph = make([][]int, x)
for i := 0; i < x; i++ {
var a, b, c, d, e int
fmt.Scanf("%d %d %d %d %d", &a, &b, &c, &d, &e)
graph[i] = []int{a, b, c, d, e}
}
visited = make([][]bool, x)
for i, _ := range visited {
visited[i] = make([]bool, y)
}
fmt.Println(graph)
var sum int
for i := 0; i < x; i++ {
for j := 0; j < y; j++ {
if !visited[i][j] && graph[i][j] == 1 {
flag = false
res = 1
dfs(graph, i, j)
if !flag {
sum += res
}
}
}
}
fmt.Println(sum)
}
func dfs(graph [][]int, x, y int) {
if graph[x][y] == 0 || visited[x][y] {
visited[x][y] = true
return
}
visited[x][y] = true
for _, dir := range dirPath {
next_x, next_y := x+dir[0], y+dir[1]
if next_x < 0 || next_x >= len(graph) || next_y < 0 || next_y >= len(graph[0]) {
flag = true // 标记岛屿挨到了边缘，不算做孤岛
continue
}
if !visited[next_x][next_y] && graph[next_x][next_y] == 1 {
if !flag {
res += 1
} else {
res = 0
}
dfs(graph, next_x, next_y)
}
}
}
沉没孤岛
本题和上题基本一致，上题目标记了孤岛，完全可以开辟一个二维数组存储岛屿的陆地，如果不是孤岛，清空数组，如果是，按照数组标记，将graph对应位置改为0 沉没 即可
水流问题
本质上判断每一个元素，(左 or 上) and (右 or 下) 满足单调递减，中间可以出现相邻元素相等
暴力解法思路，双循环遍历整个m*n矩阵，递增判断函数isordered
if (ir(graph[i][0 : j+1]) || ir(graph[0: i+1][j])) && (ir(graph[i][j : leg-1]) || ir(graph[i: wid-1][j]))
满足条件放入结果集
时间复杂度，遍历m*n*(m+n)
优化的思路
分别从上下边界出发，标记到两个数组first, second，标记规则是，从首个节点触发，能够逆流而上达到的节点（相邻节点小于等于）(使用dfs 或者 bfs)
然后左右边界出发，对同样的两个数组操作，这样first，second分别保存了第一、第二边界能够到达的所有节点
通过对比两个数组，如果节点能够同时满足第一第二边界到达，那么就收入结果集
时间复杂度m*(m*n) + n*(m*n) 这种分析是错误的
真正的时间复杂度为 由于使用了visited数组，保证了每个节点都只遍历了一次，所以应该是m*n + m*n
最大人工岛
暴力思路，分别遍历整个m*n 矩阵，尝试将每一个0 改成1 然后计算最大面积，总复杂度是m*n 次修改 * 每次修改dfs搜索拿到最大的面积 = m*m*n*n
优化思路
1，向dfs一次，为每一个岛屿打上标记(eg, 将graph数组对应陆地修改为岛屿编号)并计算面积， 这样可以得到一个map[k][v] k,v分别是岛屿编号以及岛屿面积
此时的graph也将对应的岛屿编号放入了对应的陆地中
2，暴力m*n 尝试修改每一个0 --> 1（水修改为陆地），检查修改后的四周，如果出现了岛屿编号，代表接壤了，那么计算一个新的面积为 1 + 所有接壤的岛屿面积和，对比更新最大值
总时间复杂度m*n + m*n*4(遍历每一个水改为陆地，然后向四周探查接壤) = m*n