【蓝桥杯Java真题详解】长草（BFS题型练习）

长草

题目描述

小明有一块空地，他将这块空地划分为 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.

解题思路

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int n,m,k;
	static char map[][];
	static int move[][] = new int[][] {{1,0},{0,1},{-1,0},{0,-1}};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new char[n][m];
		for (int i = 0; i < n; i++) {
			map[i]=sc.next().toCharArray();
		}
		k=sc.nextInt();
		new Main().bfs();
		for(int i=0;i<n;i++) {
			System.out.println(map[i]);
		}
		sc.close();
	}
	class A{
		int w;
		int h;
		int step;
		public A(int w,int h,int step) {
			this.w=w;
			this.h=h;
			this.step=step;
		}
	}
	private void bfs() {
		Queue<A> queue=new LinkedList<A>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j]=='g') {
					queue.offer(new A(i,j,0));
				}
			}
		}
		while (!queue.isEmpty()) {
			A a=queue.poll();
			if (a.step==k) {
				continue;
			}
			for (int i = 0; i < 4; i++) {
				int nw=a.w+move[i][0];
				int nh=a.h+move[i][1];
				int nstep=a.step+1;
				if(nw>=n||nh>=m||nw<0||nh<0)
					continue;
				if(map[nw][nh]=='g')
					continue;
				map[nw][nh]='g';
				queue.offer(new A(nw,nh,nstep));
			}
			
		}
	}

}