遍历二维矩阵

func allCellsDistOrder(R int, C int, r0 int, c0 int) [][]int

func allCellsDistOrder(R int, C int, r0 int, c0 int) [][]int {
	result := make([][]int, R*C)
	result[0] = []int{r0, c0}
	step := 1
	r, c := r0, c0
	for step < R*C {
		r--          // 从上一次遍历后的方形水波上顶点再上一步到达这次需要遍历的方形水波上顶点
		for r < r0 { // 上顶点 -> 右顶点
			if r >= 0 && c <= C-1 {
				result[step] = []int{r, c}
				step++
			}
			r++
			c++
		}
		for c > c0 { // 右顶点 -> 下顶点
			if r <= R-1 && c <= C-1 {
				result[step] = []int{r, c}
				step++
			}
			r++
			c--
		}
		for r > r0 { // 下顶点 -> 左顶点
			if r <= R-1 && c >= 0 {
				result[step] = []int{r, c}
				step++
			}
			r--
			c--
		}
		for c < c0 { // 左顶点 -> 上顶点 // 这里的判断是c<c0, 保证了不会将上顶点重复放入结果
			if r >= 0 && c >= 0 {
				result[step] = []int{r, c}
				step++
			}
			r--
			c++
		}
	}
	return result
}

// 直觉遍历，时空复杂度都是O(m*n)
func spiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return nil
	}
	const right, down, left, up = 0, 1, 2, 3
	m, n := len(matrix), len(matrix[0])
	rMin, rMax, cMin, cMax := 0, m-1, 0, n-1 // 上下左右边界
	r, c, direct := 0, 0, right
	res := make([]int, m*n)
	for i := range res {
		res[i] = matrix[r][c]
		switch direct {
		case right:
			if c < cMax {
				c++
			} else {
				direct, rMin, r = down, rMin+1, r+1
			}
		case down:
			if r < rMax {
				r++
			} else {
				direct, cMax, c = left, cMax-1, c-1
			}
		case left:
			if c > cMin {
				c--
			} else {
				direct, rMax, r = up, rMax-1, r-1
			}
		case up:
			if r > rMin {
				r--
			} else {
				direct, cMin, c = right, cMin+1, c+1
			}
		}
	}
	return res
}

	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return nil
	}
	m, n := len(matrix), len(matrix[0])
	levels := (min(m, n) + 1) / 2 //层数
	res := make([]int, 0, m*n)
	// 从外层向内层层层遍历
	for i := 0; i < levels; i++ {
		for c := i; c < n-i; c++ { // 向右
			res = append(res, matrix[i][c])
		}
		for r := i + 1; r < m-i; r++ { // 向下
			res = append(res, matrix[r][n-1-i])
		}
		for c := n - 1 - (i + 1); m-1-i != i && c >= i; c-- { // 向左；可能这一层只有一行，注意判断m-1-i 与 i是否相等
			res = append(res, matrix[m-1-i][c])
		}
		for j := m - 1 - (i + 1); n-1-i != i && j >= i+1; j-- { // 向上；可能这一层只有一列，注意判断n-1-i 与 i是否相等
			res = append(res, matrix[j][i])
		}
	}
	return res
}

func findDiagonalOrder(matrix [][]int) []int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return nil
	}
	m, n := len(matrix), len(matrix[0])
	res := make([]int, m*n)
	i := 0
	for time := 0; time <= m+n-2; time++ {
		if time%2 == 0 { // 偶数趟，r递减
			r := min(time, m-1)
			c := time - r
			for r >= 0 && c < n {
				res[i] = matrix[r][c]
				i++
				r--
				c++
			}
		} else { // 奇数趟, c递减
			c := min(time, n-1)
			r := time - c
			for c >= 0 && r < m {
				res[i] = matrix[r][c]
				i++
				c--
				r++
			}
		}
	}
	return res
}

func diagonalSort(mat [][]int) [][]int {
	m, n := len(mat), len(mat[0])
	diagonals := make(map[int][]int, m+n-1)
	for r, row := range mat {
		for c, val := range row {
			diagonals[r-c] = append(diagonals[r-c], val)
		}
	}
	for k := range diagonals {
		sort.Ints(diagonals[k])
	}
	res := make([][]int, m)
	for r := range res {
		res[r] = make([]int, n)
		for c := range res[r] {
			res[r][c] = diagonals[r-c][0]
			diagonals[r-c] = diagonals[r-c][1:]
		}
	}
	return res
}

func diagonalSort(mat [][]int) [][]int {
	m, n := len(mat), len(mat[0])
	res := make([][]int, m)
	for i := range res {
		res[i] = make([]int, n)
	}
	for i := m - 1; i >= 1-n; i-- {
		r := max(i, 0)
		c := r - i
		size := min(m-r, n-c)
		tmp := make([]int, size)
		// add elements into tmp from top-left to bottom-right
		for k := range tmp {
			tmp[k] = mat[r][c]
			r++
			c++
		}
		// add sorted elements into res from top-left to bottom-right
		sort.Ints(tmp)
		r = max(i, 0)
		c = r - i
		for k := range tmp {
			res[r][c] = tmp[k]
			r++
			c++
		}
	}
	return res
}

func generateMatrix(n int) [][]int {
	if n <= 0 {
		return nil
	}
	res := make([][]int, n)
	for i := range res {
		res[i] = make([]int, n)
	}
	levels := (n + 1) / 2
	num := 1
	for i := 0; i < levels; i++ {
		for c := i; c < n-i; c++ {
			res[i][c] = num
			num++
		}
		for r := i + 1; r < n-i; r++ {
			res[r][n-1-i] = num
			num++
		}
		for c := n - 2 - i; i != n-1-i && c >= i; c-- {
			res[n-1-i][c] = num
			num++
		}
		for r := n - 2 - i; i != n-1-i && r > i; r-- {
			res[r][i] = num
			num++
		}
	}
	return res
}

var row, column int

func spiralMatrixIII(R int, C int, r int, c int) [][]int {
	steps := 0
	row, column = R, C
	res := make([][]int, 0, R*C)
	res = append(res, []int{r, c})
	for len(res) < cap(res) {
		originR, originC := r, c
		// right
		steps++
		for k := 0; c < C && k < steps && len(res) < cap(res); k++ {
			c++
			res = checkToAppend(res, r, c)
		}
		c = originC + steps
		// down
		for k := 0; r < R && k < steps && len(res) < cap(res); k++ {
			r++
			res = checkToAppend(res, r, c)
		}
		r = originR + steps
		// left
		steps++
		for k := 0; c >= 0 && k < steps && len(res) < cap(res); k++ {
			c--
			res = checkToAppend(res, r, c)
		}
		c = originC - 1
		// up
		for k := 0; r >= 0 && k < steps && len(res) < cap(res); k++ {
			r--
			res = checkToAppend(res, r, c)
		}
		r = originR - 1
	}
	return res
}

func checkToAppend(res [][]int, r, c int) [][]int {
	if isValid(r, c) {
		res = append(res, []int{r, c})
	}
	return res
}

func isValid(r, c int) bool {
	return r >= 0 && r < row && c >= 0 && c < column
}

var row, column int
var dirs = [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

func spiralMatrixIII(R int, C int, r int, c int) [][]int {
	// right, down, left, up
	steps := 0
	row, column = R, C
	res := make([][]int, 0, R*C)
	res = append(res, []int{r, c})
	for len(res) < cap(res) {
		for i, d := range dirs {
			if i == 0 || i == 2 {
				steps++
			}
			for k := 0; k < steps; k++ {
				r, c = r+d[0], c+d[1]
				res = checkToAppend(res, r, c)
			}
		}
	}
	return res
}

func checkToAppend(res [][]int, r, c int) [][]int {
	if isValid(r, c) {
		res = append(res, []int{r, c})
	}
	return res
}

func isValid(r, c int) bool {
	return r >= 0 && r < row && c >= 0 && c < column
}