题目描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式
输入包括多个数据集合。

每个数据集合的第一行是两个整数 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
}