长草——蓝桥杯（有路数限制的最短路问题）

题目描述

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