题解 | #Shopee的办公室（二）#

package main

import "fmt"

func main() {
	x, y := 0, 0
	n := 0
	fmt.Scan(&x, &y, &n)
	var dp [31][31]int // dp[i][j] 表示从0，0到i,j的所有路径数
	bossLocation := [][2]int{}    // 该数组用于bfs和dfs算法，dp算法可忽略
	bx := 0
	by := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&bx, &by)
		bossLocation = append(bossLocation, [2]int{bx, by})
		dp[bx][by] = -1
	}

	for i := 0; i <= x; i++ {
		dp[i][0] = 1 // 很明显，从0,0 到 x,0的路径数均为1
	}
	for i := 0; i <= y; i++ {
		dp[0][i] = 1 // 很明显，从0,0 到 0,y的路径数均为1
	}

	for i := 1; i <= x; i++ {
		for j := 1; j <= y; j++ {
			if dp[i][j] == -1 {
				continue
			}
			if dp[i][j-1] != -1 {
				dp[i][j] += dp[i][j-1]
			}
			if dp[i-1][j] != -1 {
				dp[i][j] += dp[i-1][j]
			}
		}
	}
	fmt.Println(dp[x][y])

	//count := 0
	//dfs(0, 0, &count, bossLocation, x, y)
	//fmt.Println(count)
	//ret := bfs(bossLocation, x, y)
	//fmt.Println(ret)

}

func dfs(x, y int, count *int, bossLocation [][2]int, targetX, targetY int) {
	if x > targetX || y > targetY {
		return
	}
	if x == targetX && y == targetY {
		*count++
		return
	}
	if !isBossLocation(x+1, y, bossLocation) {
		dfs(x+1, y, count, bossLocation, targetX, targetY)
	}

	if !isBossLocation(x, y+1, bossLocation) {
		dfs(x, y+1, count, bossLocation, targetX, targetY)
	}

}

func isBossLocation(x, y int, bossLocation [][2]int) bool {
	for i := 0; i < len(bossLocation); i++ {
		if x == bossLocation[i][0] && y == bossLocation[i][1] {
			return true
		}
	}
	return false
}

func bfs(bossLocation [][2]int, x, y int) int {
	queue := [][2]int{}
	queue = append(queue, [2]int{0, 0}) // 初始坐标入库
	count := 0

	for len(queue) > 0 {
		front := queue[0]
		queue = queue[1:]
		if front[0] == x && front[1] == y {
			count++
		}
		if !isBossLocation(front[0]+1, front[1], bossLocation) && front[0]+1 <= x {
			queue = append(queue, [2]int{front[0] + 1, front[1]})
		}
		if !isBossLocation(front[0], front[1]+1, bossLocation) && front[1]+1 <= y {
			queue = append(queue, [2]int{front[0], front[1] + 1})
		}
	}
	return count
}