551 灌溉

 常规解法：
 

 

#include<bits/stdc++.h>
using namespace std;
int n,m,k,t;
const int N=105;
bool a[N][N],b[N][N];
int cnt;
//设置滚动数组来存贮当前和下一状态的条件
//处理传播扩散问题非常有效int main()
{cin>>n>>m>>t;for(int i=1;i<=t;i++){int x,y;cin>>x>>y;a[x][y]=1;}cin>>k;while(k--)//k次循环{for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]) b[i][j]=b[i+1][j]=b[i-1][j]=b[i][j+1]=b[i][j-1]=1;}//现在影响下一分钟的水//将自己和周围的全部更新}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=b[i][j];//将下一分钟的复制给原数组}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]) cnt++;}}cout<<cnt;return 0;
}

---

技巧性比较强：曼哈顿路径

#include<bits/stdc++.h>
using namespace std;
int n,m,t,k,ans=0;
int x[15],y[15];
//解题的思路：
/*
问在k分钟之内能灌溉多少个，
反向转化为k分钟覆盖的范围是多少，有多少个点在这个范围之内。曼哈顿距离的联系：
题目中描述的水每经过一分钟，就会向上下左右四个方向扩展一个方格，
这种扩散方式正是曼哈顿距离所描述的移动方式。为什么满足曼哈顿距离就可以
某个方格与至少一个出水管的曼哈顿距离小于等于k，那么这个方格在k分钟后就会被灌溉。
对于一个点(1,1)和另一个点(3,4)曼哈顿距离为5，具体的来说就是右走2个下走3个。
关于题目中的扩散模式，感觉上好像是同时能够向下和向右推进，但是这不是同一个点：
即向下走完3个还需要向右走2两个，向右走完2个还需要向下走3个。
*/
int main()
{cin>>n>>m>>t;for(int i = 1;i <= t;i ++)cin >> x[i] >> y[i];int k;cin>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int z=1;z<=t;z++){int d=abs(x[z]-i)+abs(y[z]-j);if(d<=k){ans++;break;}}}    }cout<<ans<<'\n';return 0;
}