题目描述
小明有一块空地，他将这块空地划分为 nn 行 mm 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，
这四小块空地都将变为有草的小块。请告诉小明，kk 个月后空地上哪些地方有草。
输入格式
输入的第一行包含两个整数 n, m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。
如果为小数点，表示为空地，如果字母为 g，表示种了草。
接下来包含一个整数 k。 其中2≤n,m≤1000，0≤k≤1000。
输出格式
输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
输入样例：
4 5
.g...
.....
..g..
.....
2
?输出样例：
gggg.
gggg.
ggggg
.ggg.做完后看了下其他大佬写的题解发现很多人用的都是queue,dfs来写的，我就在这里补充一下我用的有边数限制的最短路问题（Bellman-Ford）思想。（如果是刚刚接触的同学可以去查一下）
话不多说，上代码
#include <iostream>
#include<cstring>
#include<string>
using namespace std;
int ne[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int a[1005][1005],backup[1005][1005];//backup是备份数组，因为当月在空地上中的草，不能在当月
//向周围种草，所以得用备份数组维持原来的状态
int main()
{
// 请在此输入您的代码
int n,m;cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
char ch;cin>>ch;
if(ch=='.') a[i][j]=0;//将'.'换成0来表示空地
else a[i][j]=1;//将'g'换成1来表示已种草
}
}
int k;cin>>k;
for(int i=0;i<k;i++)
{
memcpy(backup,a,sizeof a);//将当月a的原始状态拷贝给backup
for(int j=0;j<n;j++)
{
for(int j1=0;j1<m;j1++)
{
if(backup[j][j1]==0&&a[j][j1]==0)//如果a[j][j1]=1,backup[j][j1]=0,说明就a[j][j1]的
//草是刚种下去的
{
for(int j2=0;j2<=3;j2++)
{
int tx=j+ne[j2][0],ty=j1+ne[j2][1];
if(tx>=0&&tx<n&&ty>=0&&ty<m&&a[tx][ty]==1&&backup[tx][ty]==1)
{
a[j][j1]=1;
break;
}
}
}
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]==0) cout<<'.';
else cout<<'g';
}
cout<<endl;
}
return 0;
}