家政网站设计,上海网站维护,网站后台管理系统制作教程,襄阳优化公司常规解法#xff1a; #includebits/stdc.h
using namespace std;
int n,m,k,t;
const int N105;
bool a[N][N],b[N][N];
int cnt;
//设置滚动数组来存贮当前和下一状态的条件
//处理传播扩散问题非常有效int main()
{cinnmt;for(int i1;i #includebits/stdc.h
using namespace std;
int n,m,k,t;
const int N105;
bool a[N][N],b[N][N];
int cnt;
//设置滚动数组来存贮当前和下一状态的条件
//处理传播扩散问题非常有效int main()
{cinnmt;for(int i1;it;i){int x,y;cinxy;a[x][y]1;}cink;while(k--)//k次循环{for(int i1;in;i){for(int j1;jm;j){if(a[i][j]) b[i][j]b[i1][j]b[i-1][j]b[i][j1]b[i][j-1]1;}//现在影响下一分钟的水//将自己和周围的全部更新}for(int i1;in;i){for(int j1;jm;j){a[i][j]b[i][j];//将下一分钟的复制给原数组}}}for(int i1;in;i){for(int j1;jm;j){if(a[i][j]) cnt;}}coutcnt;return 0;
} 技巧性比较强曼哈顿路径
#includebits/stdc.h
using namespace std;
int n,m,t,k,ans0;
int x[15],y[15];
//解题的思路
/*
问在k分钟之内能灌溉多少个
反向转化为k分钟覆盖的范围是多少有多少个点在这个范围之内。曼哈顿距离的联系
题目中描述的水每经过一分钟就会向上下左右四个方向扩展一个方格
这种扩散方式正是曼哈顿距离所描述的移动方式。为什么满足曼哈顿距离就可以
某个方格与至少一个出水管的曼哈顿距离小于等于k那么这个方格在k分钟后就会被灌溉。
对于一个点(1,1)和另一个点(3,4)曼哈顿距离为5具体的来说就是右走2个下走3个。
关于题目中的扩散模式感觉上好像是同时能够向下和向右推进但是这不是同一个点
即向下走完3个还需要向右走2两个向右走完2个还需要向下走3个。
*/
int main()
{cinnmt;for(int i 1;i t;i )cin x[i] y[i];int k;cink;for(int i1;in;i){for(int j1;jm;j){for(int z1;zt;z){int dabs(x[z]-i)abs(y[z]-j);if(dk){ans;break;}}} }coutans\n;return 0;
}
