【BFS】长草

题目

---

小明有一块空地，他将这块空地划分为 $n$ 行 $m$ 列的小块，每行和每列的长度都为 $1$。

小明旋律其中一小块空地，种上了草，其他小块仍然保持是空地。

这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它会向自己的上、下、左、右四小块空地扩展。

这四小块空地都将变为有草的小块。请告诉小明，$k$ 个月后空地上哪些地方有草。

输入格式

输入的第一行包含两个整数 $n, m$。

接下来 $n$ 行，每行包含 $m$ 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 $g$，表示种了草。

接下来包含一个整数 $k$。

输出格式

输出 $n$ 行，每行包含 $m$ 个字母，表示 $k$ 个月后空地的状态。如果为小数点，表示为空地，如果字母为$ g$，表示长了草。

数据范围

对于 30% 的评测用例，$2 <= n, m <= 20$。

对于 70% 的评测用例，$2 <= n, m <= 100$。

对于所有评测用例，$2 <= n, m <= 1000，1 <= k <= 1000$。

输入样例：

4 5
.g...
.....
..g..
.....
2

输出样例：

gggg.
gggg.
ggggg
.ggg.

解题

方法一：BFS

思路

本题是 BFS 模板题，读入草地后遍历，把种草的点创建为状态（包含坐标和月数）加入到队列，然后从队列中逐个取出，如果取出格子的月数小于 k，就枚举其四个方向进行扩张，把其中合法（没越界，当前不是 'g'）的点在草地中改为 'g' 并创建为状态加入到队列（月数增加），重复这个过程直到队列为空后输出草地。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static int n, m;
    static char[][] g;
    static int k;

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(Reader.next());
        m = Integer.parseInt(Reader.next());
        g = new char[n][m];
        for (int i = 0; i < n; ++i) {
            g[i] = Reader.nextLine().toCharArray();
        }
        k = Integer.parseInt(Reader.next());
        bfs();
        StringBuilder ans = new StringBuilder();
        for (char[] line : g) {
            ans.append(String.valueOf(line)).append("\n");
        }
        System.out.print(ans);
    }

    static void bfs() {
        Queue<int[]> que = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // 找到初始状态已经长草了点格子 创建状态: 前两个元素表示坐标 后一个元素表示步数
                if (g[i][j] == 'g') que.offer(new int[]{i, j, 0});
            }
        }
        while (!que.isEmpty()) {
            int[] state = que.poll(); // 取出状态
            int cnt = state[2];
            if (cnt++ < k) { // 月数增加
                // 枚举四个方向进行扩张
                for (int[] d : DIRECTIONS) {
                    int nx = state[0] + d[0], ny = state[1] + d[1];
                    // 得出的格子非法就剪枝
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == 'g') continue;
                    g[nx][ny] = 'g'; // 格子长草
                    que.offer(new int[]{nx, ny, cnt}); // 加入队列
                }
            }
        }
    }

    static class Reader {
        static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer in = new StringTokenizer("");

        static String next() throws IOException {
            while (!in.hasMoreTokens()) {
                in = new StringTokenizer(BR.readLine());
            }
            return in.nextToken();
        }

        static String nextLine() throws IOException { return BR.readLine(); }
    }
}