長草
題目描述
小明有一塊空地，他將這塊空地劃分為 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));
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/272873.html
標籤：java