BZOJ5217: [Lydsy2017省队十连测]航海舰队

Description

Byteasar 组建了一支舰队！他们现在正在海洋上航行着。海洋可以抽象成一张n×m 的网格图，其中有些位置是“

.”，表示这一格是海水，可以通过；有些位置是“#”，表示这一格是礁石，不可以通过；有些位置是“o”，表

示这一格目前有一艘舰，且舰离开这一格之后，这一格将变为“.”。这些“o” 表示Byteasar 的舰队，他们每天

可以往上下左右中的一个方向移动一格，但不能有任何一艘舰驶出地图。特别地，Byteasar 对阵形有所研究，所

以他不希望在航行的过程中改变阵形，即任何时刻任何两艘舰的相对位置都不能发生变化。Byteasar 的舰队可以

航行无限长的时间，每当一艘舰经过某个格子的时候，这个格子海底的矿藏都将被Byteasar 获得。请写一个程序

，帮助Byteasar 计算他最多可以获得多少个格子海底的矿藏？

Input

第一行包含两个正整数n;m，分别表示地图的长和宽。n, m <= 700

接下来n 行，每行有m 个字符，每个字符只能是“.”、“#”、“o” 中的一个。

输入数据保证至少有一个“o”。

Output

输出一行一个整数，即可以被经过的格子数的最大值。

Sample Input

4 5
....#
.o#.o
.o..o
..o..

Sample Output

前一天才见过的套路，第二天就考了，太碰巧了。

想着想着就会发现能放舰队的地方一定是全部是点才行，相当于一个通配符匹配！

呃，通配符匹配？我好想会FFT：见这里，反手就是一个FFT板子。

等等……它没问我经过多少格子，问的是覆盖了多少格子

………………………………突然尴尬………………………………

还好，马上就想到了再用一个多项式乘法统计答案：因为现在的操作相当于从每一个能放的地方开始都放一个舰队的字符串，如果把能放的位置和舰队中的船全部看成1，那么就相当于一个多项式乘法，这样乘出来看非0位就是能被覆盖的地方了！

注意为了避免舰队穿过右边版面到左边的情况，要把这些位置开头的舰队放置方案清零。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<complex>
#include<cmath>
#define LL long long
using namespace std;
const double Pi = acos(-1);
const int maxn = 1e6 + 5;

struct E {
	#define T double
	T real, imag; E(){}
	E(T x, T y) {real = x, imag = y;}
	E operator + (const E &A) const {
		return (E){real + A.real, imag + A.imag};
	}
	E operator - (const E &A) const {
		return (E){real - A.real, imag - A.imag};
	}
	E operator * (const E &A) const {
		return (E){real * A.real - imag * A.imag, real * A.imag + imag * A.real};
	}
};

char mp[705][705], ship[705][705];
char s[maxn << 1], t[maxn << 1];
int n, m, cnt;
E sn[maxn << 1], tn[maxn << 1], tmp[maxn << 1];
E sn2[maxn << 1], tn2[maxn << 1], tn3[maxn << 1];
double sum;
int ans[maxn << 1], vis[705][705];
int omnx = 0x3f3f3f3f, omny = 0x3f3f3f3f, omxx, omxy;

namespace match {
	int n, m, lt[705][705], acc[705][705];
	int dx[4] = {0, 0, -1, 1};
	int dy[4] = {-1, 1, 0, 0};
	void dfs(int x, int y) {
		int nx, ny;
		acc[x][y] = 1;
		for(register int i = 0; i < 4; ++i) {
			nx = x + dx[i];
			ny = y + dy[i];
			if(!lt[nx][ny]) continue;
			if(acc[nx][ny]) continue;
			dfs(nx, ny);
		}
	}
	namespace FFT {
		int RL[maxn << 1], N, mxp;
		void init(int n) {
			for(N = 1, mxp = 0; N < n; N <<= 1, ++mxp);
			for(register int i = 1; i <= N; ++i) 
				RL[i] = (RL[i >> 1] >> 1) | ((i & 1) << mxp - 1);
			return ;
		}
		void FFT(E * A, int type) {
			for(register int i = 0; i < N; ++i)
				if(i < RL[i]) swap(A[i], A[RL[i]]);
			E Wn, w, x, y;
			for(register int i = 1; i < N; i <<= 1) {
				Wn = E(cos(Pi / i), sin(Pi / i) * type);
				for(register int j = 0, p = i << 1; j < N; j += p) {
					w = E(1, 0);
					for(register int k = 0; k < i; ++k, w = w * Wn) {
						x = A[j + k], y = w * A[j + k + i];
						A[j + k] = (x + y), A[j + k + i] = (x - y);
					}
				}
			}
		}
		void calc(E * sn2, E * tn, E * sn, E * tn2, int n, int m) {
			init(n + m);
			FFT(sn2, 1), FFT(tn, 1), FFT(tn2, 1), FFT(sn, 1);
			for(register int i = 0; i <= N; ++i)
				sn2[i] = sn2[i] * tn[i] - E(2, 0) * tn2[i] * sn[i];
			FFT(sn2, -1);
			for(register int i = 0; i <= N; ++i)
				sn2[i].real /= N;
		}
		void mul(E * A, E * B, int n, int m) {
			init(n + m);
			FFT(A, 1), FFT(B, 1);
			for(register int i = 0; i <= N; ++i)
				A[i] = A[i] * B[i];
			FFT(A, -1);
			for(register int i = 0; i <= N; ++i)
				A[i].real /= N;
		}
	}
	int work() {
		n = strlen(s) - 1, m = strlen(t) - 1;
		int u;
		for(register int i = 0; i <= n; ++i) {
			u = n - i;
			sn[u].real = s[i] == '#' ? 1 : 2;
			sn2[u].real = sn[u].real * sn[u].real;
		}
		for(register int i = 0; i <= m; ++i) {
			if(t[i] == '?') tn[i].real = 0;
			else tn[i].real = 2;
			tn2[i].real = tn[i].real * tn[i].real;
			tn3[i].real = tn[i].real * tn2[i].real;
			sum += tn3[i].real;
		}
		memcpy(tmp, tn, sizeof(tn));
		FFT::calc(sn2, tmp, sn, tn2, n + 1, n + 1);
		reverse(sn2, sn2 + n + 1);
		for(register int i = 0; i <= n; ++i) {
			ans[i] = !(((int)(sn2[i].real + sum + 0.5)) != 0);
		}
		int tot = 0;
		for(register int i = 0; i < ::n; ++i) {
			for(register int j = 0; j < ::m; ++j) {
				++tot;
				if(i < ::n - (omxx - omnx) && j < ::m - (omxy - omny))
					{lt[i][j] = ans[tot - 1]; continue;}
				lt[i][j] = 0;
			}
		}
		memset(tmp, 0, sizeof(tmp));
		dfs(omnx, omny), tot = 0;
		for(register int i = 0; i < ::n; ++i)
			for(register int j = 0; j < ::m; ++j) {
				if(!acc[i][j]) ans[tot] = 0;
				tmp[tot].real = ans[tot], ++tot;
			}
		FFT::mul(tmp, tn, n - m + 1, m + 1);
		return 0;
	}
}	

int main() {
	//freopen("sailing.in", "r", stdin);
	//freopen("sailing.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(register int i = 0; i < n; ++i)
		scanf("%s", mp[i]);
	for(register int i = 0; i < n; ++i)
		for(register int j = 0; j < m; ++j) {
			if(mp[i][j] == 'o') {
				omnx = min(omnx, i);
				omxx = max(omxx, i);
				omny = min(omny, j);
				omxy = max(omxy, j);
			}
		}
	for(register int j = omny; j < m; ++j) {
		if(mp[omnx][j] == 'o') t[cnt] = '.';
		else t[cnt] = '?';
		++cnt;
	}
	for(register int i = omnx + 1; i < omxx; ++i)
		for(register int j = 0; j < m; ++j) {
			if(mp[i][j] == 'o') t[cnt] = '.';
			else t[cnt] = '?';
			++cnt;
		}
	for(register int j = 0; j < m; ++j) {
		if(mp[omxx][j] == 'o') t[cnt] = '.';
		else t[cnt] = '?';
		++cnt;
	}
	t[cnt] = 0, cnt = 0;
	for(register int i = 0; i < n; ++i)
		for(register int j = 0; j < m; ++j) {
			mp[i][j] = mp[i][j] == 'o' ? '.' : mp[i][j];
			s[cnt] = mp[i][j], ++cnt;
		}
	s[cnt] = 0;
	match::work();
	int tot = 0, lans = 0;
	for(register int i = 0; i < n; ++i)
		for(register int j = 0; j < m; ++j)
			if((int)(tmp[tot++].real)) ++lans;
	printf("%d", lans);
	return 0;
}

Rockdu's Blog