题目描述
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。
请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时,表示输入结束。
输出格式
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围
1≤W,H≤20
样例
输入样例
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例
45
算法1
深度优先搜索
递归
Golang 代码
package main
import "fmt"
func main() {
for {
var w, h int
fmt.Scan(&w, &h)
if w == 0 && h == 0 {
return
}
grids := make([][]byte, h)
for i := 0; i < h; i++ {
grids[i] = make([]byte, w)
}
// 起始点坐标
var startX, startY int
for i := 0; i < h; i++ {
fmt.Scan(&grids[i])
for j := 0; j < w; j++ {
if grids[i][j] == '@' {
startX, startY = i, j
}
}
}
res := bfs(startX, startY, grids)
fmt.Println(res)
}
}
func dfs(x int, y int, grids [][]byte) int {
m, n := len(grids), len(grids[0])
dx := [4]int{-1, 0, 0, 1}
dy := [4]int{0, -1, 1, 0}
res := 1
grids[x][y] = '#'
for i := 0; i < 4; i++ {
newX, newY := x + dx[i], y + dy[i]
if newX >= 0 && newX < m && newY >= 0 && newY < n && grids[newX][newY] == '.' {
res += dfs(newX, newY, grids)
}
}
return res
}
算法2
广度优先搜索
采用队列的方式
Golang 代码
package main
import "fmt"
func main() {
for {
var w, h int
fmt.Scan(&w, &h)
if w == 0 && h == 0 {
return
}
grids := make([][]byte, h)
for i := 0; i < h; i++ {
grids[i] = make([]byte, w)
}
// 起始点坐标
var startX, startY int
for i := 0; i < h; i++ {
fmt.Scan(&grids[i])
for j := 0; j < w; j++ {
if grids[i][j] == '@' {
startX, startY = i, j
}
}
}
res := bfs(startX, startY, grids)
fmt.Println(res)
}
}
func bfs(x int, y int, grids [][]byte) int {
dx, dy := [4]int{-1, 0, 0, 1}, [4]int{0, -1, 1, 0}
m, n := len(grids), len(grids[0])
var res int
queue := make([][2]int, 0)
queue = append(queue, [2]int{x, y})
grids[x][y] = '#'
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:len(queue)]
res++
for i := 0; i < 4; i++ {
newX, newY := cur[0] + dx[i], cur[1] + dy[i]
if newX >= 0 && newX < m && newY >= 0 && newY < n && grids[newX][newY] == '.' {
queue = append(queue, [2]int{newX, newY})
grids[newX][newY] = '#'
}
}
}
return res
}