蓝桥杯：长草 ← DFS

【题目来源】
https://www.lanqiao.cn/problems/149/learning/

【问题描述】
小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。

【输入格式】
输入的第一行包含两个整数 n，m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
接下来包含一个整数 k。 其中，2≤n, m≤1000，1≤k≤1000。

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

【BFS解法】
本题的BFS解法，可参见我之前的博客：https://blog.csdn.net/hnjzsyjyj/article/details/128116925
当然，本题也可以采用DFS解法。详见下文。

【DFS算法代码框架】

void dfs(int step) {判断边界 {输出解}尝试每一种可能 {满足check条件{标记继续下一步：dfs(step+1)恢复初始状态（回溯的时候要用到）}}
}

【DFS算法代码】

#include<bits/stdc++.h>
using namespace std;const int maxn=1005;
char a[maxn][maxn];
int n,m;
int dx[4]= {-1,0,1,0};
int dy[4]= {0,1,0,-1};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(tx<0 || ty<0 || tx>=n || ty>=m || a[tx][ty]=='g') continue;a[tx][ty]='g';dfs(tx,ty,k-1);}
}int main() {cin>>n>>m;int row[n*m],col[n*m];int cnt=0;for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {cin>>a[i][j];if(a[i][j]=='g') {row[cnt]=i;col[cnt]=j;cnt++;}}}int k;cin>>k;for(int i=0; i<cnt; i++) {dfs(row[i],col[i],k);}for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {cout<<a[i][j];}cout<<endl;}return 0;
}/*
in:
4 5
.g...
.....
..g..
.....
2out:
gggg.
gggg.
ggggg
.ggg.
*/