NBUT 1618 投放炸弹（树状数组）

[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;

}

巴特西

NBUT 1618 投放炸弹（树状数组）

[1618] 投放炸弹

最新文章

热门文章