733. 图像渲染

解题思路：然每个节点进行广度或深度遍历，这里需要注意一个边界问题防止重复添加到访问，这个要点在把不同颜色判断为需要遍历的节点

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
    lenc := len(image[0])
	lenr := len(image)

	if sr > lenr-1 || sc > lenc-1 {
		return image
	}

	centerColor := image[sr][sc]

	if centerColor == newColor {
		return image
	}

	// 上左下右顺序深度遍历
	image[sr][sc] = newColor

	// 记录遍历的点
	queue := [][]int{{sr, sc}}
	// fmt.Println(queue, image)
	// 从rc rs 出发
	for i := 0; i < len(queue); i++ {
		pos := queue[i]

		// 上
		if pos[0]-1 >= 0 && image[pos[0]-1][pos[1]] == centerColor {
			// fmt.Println("上")
			queue = append(queue, []int{pos[0] - 1, pos[1]})
			image[pos[0]-1][pos[1]] = newColor
		}
		// 右
		if pos[1]+1 < lenc && image[pos[0]][pos[1]+1] == centerColor {
			// fmt.Println("右")
			queue = append(queue, []int{pos[0], pos[1] + 1})
			image[pos[0]][pos[1]+1] = newColor
		}
		// 下
		if pos[0]+1 < lenr && image[pos[0]+1][pos[1]] == centerColor {
			// fmt.Println("下")
			queue = append(queue, []int{pos[0] + 1, pos[1]})
			image[pos[0]+1][pos[1]] = newColor
		}
		// 左
		if pos[1]-1 >= 0 && image[pos[0]][pos[1]-1] == centerColor {
			// fmt.Println("左")
			queue = append(queue, []int{pos[0], pos[1] - 1})
			image[pos[0]][pos[1]-1] = newColor
		}
		// fmt.Println(queue)
	}
	return image
}


时间复杂度：O(n x m)O(n×m)，其中 nn 和 mm 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。

空间复杂度：O(n x m)O(n×m)，其中 nn 和 mm 分别是二维数组的行数和列数。主要为队列的开销。

695. 岛屿的最大面积

解题思路：图的遍历都需要考虑一个是否访问过的问题，因此提也是通过对比值进行，把访问过的变位0，就不会在访问统计队列中

时间复杂度：O(n x m)O(n×m)， 空间复杂度：O(n x m)O(n×m)

nn 和 mm 分别是二维数组的行数和列数

总结

解题思路，广度优先搜索 / 深度优先搜索，都是需要考虑边界问题，防止重复访问，需要遍历全部并且需要额外的存储空间