java 实现蓝桥杯模拟空地长草 DFS_蓝桥杯：长草 dfs

空地长草

求解方法 dfs。
题目：
  小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
　　小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
　　这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。
　　请告诉小明，k 个月后空地上哪些地方有草。
　　
输入：
  输入的第一行包含两个整数 n, m。接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
　　接下来包含一个整数 k。

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

数据规模：
  对于 30% 的评测用例，2 <= n, m <= 20。
　　对于 70% 的评测用例，2 <= n, m <= 100。
　　对于所有评测用例，2 <= n, m <= 1000，1 <= k <= 1000。

1.记录g位置数组的使用(空间换时间)
		row=new int[n*m];
		col=new int[n*m];
		int temp=0;
		再次访问时直接循环到temp记录的位置即可
1
2
3
4
5

eg:
样例输入

4 5
.g...
.....
..g..
.....
2
1
2
3
4
5
6

样例输出

gggg.
gggg.
.gggg
.ggg.
1
2
3
4

代码(java)

package DFS;
import java.util.*;
//蓝桥杯模拟赛空地长草

public class Test4 {
//	定义二维数组
	public static int n;
	public static int m;
	public static int kmax;
	public static char[][] ch;
	public static int[] row;
	public static int[] col;
	
//	定义移动数组,顺时针，上下左右
	public static int[] dx= {-1,0,1,0};
	public static int[] dy= {0,1,0,-1};
	
//	定义检查函数
	public static boolean Check(int x,int y) {
		if(x>=0&&x<n&&y>=0&&y<m) {
			return true;
		}
		return false;
	}
	
//	dfs
	public static void dfs(int x,int y,int k) {
		if(k==0) {
			return;
		}
		for(int i=0;i<4;i++) {			
			int tx=x+dx[i];
			int ty=y+dy[i];
			
			if(Check(tx, ty)&&ch[tx][ty]=='.') {
				ch[tx][ty]='g';
				dfs(tx,ty,k-1);
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
//		吸收回车符号
		String str=sc.nextLine();
				
		ch=new char[n][m];
		//空间换时间
		row=new int[n*m];
		col=new int[n*m];
		int temp=0;
		
		for(int i=0;i<n;i++) {
			ch[i]=sc.nextLine().toCharArray();
			for(int j=0;j<m;j++) {
				if(ch[i][j]=='g') {
					//记录下g的位置，并标记此处已长草
					row[temp]=i;
					col[temp++]=j;	//先赋值，后加1
				}
			}
		}
		
//		天数
		kmax=sc.nextInt();
		
		for(int i=0;i<temp;i++) {
			dfs(row[i],col[i],kmax);
		}
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				System.out.print(ch[i][j]);
			}
			System.out.println();
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81