当前位置：首页 > article >正文

蓝桥杯31天真题冲刺|题解报告|第二十三天

article 2025/1/11 22:51:59

大家好，我是snippet，今天是刷蓝桥真题的第二十三天，今天的题基本上都包含搜索，下面是我今天的题解

一、长草

题目描述

输入描述

输出描述

输入输出样例

运行限制

二、蓝肽子序列

三、迷宫与陷阱

四、送礼物

一、长草

题目链接：长草 - 蓝桥云课 (lanqiao.cn)

题目内容：

题目描述

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

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

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

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

输入描述

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

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

接下来包含一个整数 k。其中，2≤n,m≤1000，1≤k≤1000。

输出描述

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

输入输出样例

示例

输入

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

输出

gggg.
gggg.
ggggg
.ggg.

运行限制

最大运行时间：1s
最大运行内存: 256M

解题思路：

这个题感觉跟灌溉差不多，可以直接用dfs

代码：

package 蓝桥杯31天真题冲刺.Day23;

import java.io.*;

/**
 * @author snippet
 * @data 2023-03-26
 * 长草-蓝桥云课
 */
public class T1_长草 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    static int n,m,k;
    static int N = 1010;
    static char[][] c = new char[N][N];
    static boolean[][] is = new boolean[N][N];
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    static void dfs(int x, int y) {
        for (int i = 0; i < 4; i++) {
            if ((x + dx[i]) > 0 && (x + dx[i]) <= n && (y + dy[i]) > 0 && (y + dy[i]) <= m && c[x+dx[i]][y+dy[i]] == '.' && !is[x+dx[i]][y+dy[i]]) {
                c[x+dx[i]][y+dy[i]] = 'g';
                is[x+dx[i]][y+dy[i]] = true;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 1; i <= n; i++) {
            s = br.readLine().split(" ");
            for (int j = 1; j <= m; j++) {
                c[i][j] = s[0].charAt(j-1);
            }
        }
        k = Integer.parseInt(br.readLine().split(" ")[0]);
        while (k-- > 0) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (c[i][j] == 'g'&& !is[i][j]) {
                        is[i][j] = true;
                        dfs(i, j);
                    }
                }
            }
            is = new boolean[N][N];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (c[i][j] == 'g') pw.print('g');
                else pw.print('.');
            }
            pw.println();
        }
        pw.flush();
        br.close();
    }
}