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

蓝桥杯—草坪(模拟+bfs分层处理)

article 2025/4/2 4:18:52

一.题目

二.代码

三.错误分析

一.题目

分析:一眼bfs向上下左右四个方向扩散生长，典型的bfs算法，这里需要注意的是需要分层处理

，每一层代表一个月

二.代码

import java.util.Scanner;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static int[] dx = {0,1,-1,0};
    public static int[] dy = {1,0,0,-1};
    static class pair{
        int x;
        int y;
        public pair(int x,int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        char[][] map = new char[n][m];
        scan.nextLine();
        for(int i = 0;i<n;i++)
        {
            map[i] = scan.nextLine().toCharArray();//将地图信息录入
        }
        int k = scan.nextInt();//k个月,每个月会向上下左右扩展一次
        //输出结果,结果保留在map数组中
        bfs(map,n,m,k);
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            System.out.print(map[i][j]);
            System.out.println();
        }
        scan.close();
    }
    public static void bfs(char[][] map,int n,int m,int k)
    {
        Queue<pair> queue = new LinkedList<>();
        //记录一轮
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                if(map[i][j]=='g')
                {
                    queue.add(new pair(i,j));//将初始有草的地全部入队
                }
            }
        }
        while(!queue.isEmpty()&&k!=0)
        {
          int cnt = queue.size();
          for(int j = 0;j<cnt;j++)//分层处理
          {
            pair top = queue.poll();//出队
            for(int i = 0;i<4;i++)//向四周蔓延
            {
                int xx = top.x + dx[i];
                int yy = top.y + dy[i];
                if(cheak(xx,yy,map))
                {
                    map[xx][yy] = 'g';
                    queue.add(new pair(xx,yy));
                }
            }
          }
          k--;
        }
    }
    public static boolean cheak(int x,int y,char[][] map)//减枝函数
    {
        if(x>=0&&x<map.length&&y>=0&&y<map[0].length&&map[x][y]!='g')
            return true;
        return false;
    }
}