[1618] 投放炸弹
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
- 我们定义一个炸弹能炸毁的地方要求曼哈顿距离小于等于某个值。
曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离，即d（i，j）=|xi-xj|+|yi-yj|。-来自百度百科
现在给出一个n*m的平面图，'.'表示无人区，'*'表示居民区。炸弹只能投放在无人区，炸弹能炸毁曼哈顿距离小于等于x的所有居民区，现在你要来投放这个炸弹，请输出炸弹最多能炸毁的居民区个数。 - 输入
- 多组输入，每组第一行n,m,x。
接下来输入n行，每行m个字符，字符只有'.'和'*'。
数据范围：1<=n,m<=200,1<=x<=1e9 - 输出
- 每组输出一行，最多可以炸毁的居民区个数。
- 样例输入
4 5 1
..*..
**.**
..*..
.....
2 3 4
***
***- 样例输出
4
0
题目链接：NBUT 1618
大一那会儿留下来的题目，最近想学KDtree突然想起来这题……很那啥的一道题，佩服作者的YY能力，实际上题目中炸弹范围是一个菱形，如果忽略地图边界，还是一个完全对称的菱形，DFS的话T了很多发，这题如果仔细想想是可以用二维树状数组做的，T[i][j]维护第i行前j个格子中含有居民点的前缀和，菱形内的居民区个数可以从上到下一行一行地求出来，当然这题有个小坑就是范围可以很大，那么根据题目实际地图大小缩小到实际可以使用的范围就好了。求和的时候个别边界出现负数处理一下即可
代码：
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <numeric>
#include <cstring>
#include <bitset>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 210;
int T[N][N];
char s[N][N];
int n, m; void init()
{
CLR(T, 0);
}
void add(int h, int k, int v)
{
while (k < N)
{
T[h][k] += v;
k += (k & -k);
}
}
int getsum(int h, int k)
{
if (k <= 0)
return 0;
int ret = 0;
if (k > m)
k = m;
while (k)
{
ret += T[h][k];
k -= (k & -k);
}
return ret;
}
int main(void)
{
int k, i, j;
while (~scanf("%d%d%d", &n, &m, &k))
{
init();
for (i = 1; i <= n; ++i)
{
scanf("%s", s[i] + 1);
for (j = 1; j <= m; ++j)
{
if (s[i][j] == '*')
add(i, j, 1);
}
}
int ans = 0;
k = min(k, max(n, m));
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= m; ++j)
{
if (s[i][j] == '.')
{
int temp = getsum(i, j + k) - getsum(i, j - k - 1);
for (int kk = 1; kk <= k; ++kk)
{
int up = i - kk, down = i + kk;
if (up >= 1)
temp += getsum(up, j + k - kk) - getsum(up, j - k - 1 + kk);
if (down <= n)
temp += getsum(down, j + k - kk) - getsum(down, j - k - 1 + kk);
}
if (temp > ans)
ans = temp;
}
}
}
printf("%d\n", ans);
}
return 0;
}