侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】长草

GabrielxD
2022-10-04 / 0 评论 / 0 点赞 / 18 阅读 / 890 字 / 正在检测是否收录...

题目


小明有一块空地,他将这块空地划分为 nnmm 列的小块,每行和每列的长度都为 11

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

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

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

输入格式

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

接下来 nn 行,每行包含 mm 个字母,表示初始的空地状态,字母之间没有空格。如果为小数点,表示为空地,如果字母为 gg,表示种了草。

接下来包含一个整数 kk

输出格式

输出 nn 行,每行包含 mm 个字母,表示 kk 个月后空地的状态。如果为小数点,表示为空地,如果字母为$ g$,表示长了草。

数据范围

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

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

对于所有评测用例,2<=n,m<=10001<=k<=10002 <= 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(); }
    }
}

0

评论区