AHSDFZ 模拟赛航海舰队 sailing

Description

Byteasar 组建了一支舰队！他们现在正在海洋上航行着。

海洋可以抽象成一张n×m 的网格图，其中有些位置是”.”，表示这一格是海水，可以通过；有些位置是”#”，表示这一格是礁石，不可以通过；有些位置是”o”，表示这一格目前有一艘舰，且舰离开这一格之后，这一格将变为”.”。

这些”o” 表示Byteasar 的舰队，他们每天可以往上下左右中的一个方向移动一格，但不能有任何一艘舰驶出地图。特别地，Byteasar 对阵形有所研究，所以他不希望在航行的过程中改变阵形，即任何时刻任何两艘舰的相对位置都不能发生变化。

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

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

Input

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

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

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

Output

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

Sample Input

1
2
3
4
5
4 5
....#
.o#.o
.o..o
..o..

Sample Output

1
12

Hint

Source

2017省选前集训 by Claris

Solution

FFT。

首先因为阵型是固定的，我们不妨将棋盘拉成一条长链。若阵型在其中的x0,x0+a1,x0+a2….处，那么我们改变x0，检查匹配时ai不变。如果可以匹配，对应棋盘中这些位置都为’.’。

于是求有多少位置合法就变成了一个字符串匹配问题。我们将阵型串反转，用FFT求出每个地方不合法数目。如果为0，则这个地方可以作为舰队的头所在位置。

考虑计算答案。

我们继续做FFT，这个FFT求的是一个地方被覆盖了多少次。用阵型串原串与棋盘卷积即可。

注意多项式乘完后的下标表示什么含义，不要被坑了。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Complex {
    double x, y; Complex() {} Complex (double xx, double yy) {x=xx; y=yy;}
    Complex operator + (Complex a) {return Complex(x + a.x, y + a.y);}
    Complex operator - (Complex a) {return Complex(x - a.x, y - a.y);}
    Complex operator * (Complex a) {return Complex(x * a.x - y * a.y, x * a.y + y * a.x);}
} A[2111111], B[2111111], C[2111111], D[2111111];
const double pi = acos(-1);
int n, m, N, L, tot, R[2111111], a[2111111], b[2111111], c[705][705], d[705][705];
char str[705][705];
void dft(Complex *a, double f) {
    for (int i = 1; i < N; ++i) if (i > R[i]) swap(a[i], a[R[i]]);
    for (int i = 1; i < N; i <<= 1) {
        Complex wn(cos(pi / i), f * sin(pi / i));
        for (int j = 0; j < N; j += (i << 1)) {
            Complex w(1, 0);
            for (int k = 0; k < i; ++k) {
                Complex x = a[j + k], y = a[j + k + i] * w;
                a[j + k] = x + y;
                a[j + k + i] = x - y;
                w = w * wn;
            }
        }
    }
}
int X[705*705], Y[705*705], sx, sy, id[705][705], ex, ey;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};
void dfs(int nx, int ny) {
    if (nx<=0||ny<=0||nx>=n||ny>=m) return;
    if (c[nx-ex+sx][ny-ey+sy]) return;
    if (d[nx][ny]) return;
    c[nx-ex+sx][ny-ey+sy] = true;
    for (int i = 0; i < 4; ++i)
        dfs(nx+dx[i],ny+dy[i]);
}
int main() {
    freopen("sailing.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%s", str[i] + 1);
    ++n; ++m;
    for (int i = 0; i <= m; ++i) str[0][i] = str[n][i] = '#';
    for (int i = 0; i <= n; ++i) str[i][0] = str[i][m] = '#';
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (str[i][j] == 'o') {
                if (sx == 0) { sx = i; sy = j; } ex = i; ey = j;
                b[tot] = 1; str[i][j] = '.';
            }
            a[tot] = A[tot].x = str[i][j] == '#';
            X[tot] = i;
            Y[tot] = j;
            id[i][j] = tot++;
        }
    }
    int fst=-1, lst;
    for (int i = 0; i < tot; ++i) { if (b[i] == 1) { if (fst==-1) fst = i; lst = i; } }
    for (int i = 0; i+fst < tot; ++i) b[i] = b[i+fst]; lst -= fst;
    for (int i = tot-fst; i < tot; ++i) b[i] = 0;
    for (int i = 0; i < tot; ++i) D[i].x = b[i];
    for (int i = 0, j = lst; i < j; ++i, --j) swap(b[i], b[j]);
    for (int i = 0; i < tot; ++i) B[i].x = b[i];
    for (L=-1,N=1;N<=tot*2;++L,N<<=1);
    for (int i = 1; i < N; ++i) R[i] = (R[i>>1]>>1)|((i&1)<<L);
    dft(A, 1); dft(B, 1); for (int i = 0; i < N; ++i) A[i] = A[i] * B[i]; dft(A, -1); for (int i = 0; i < N; ++i) A[i].x /= N;
    for (int i = 1; i < n; ++i)
        for (int j = 1; j < m; ++j)
            d[i][j] = A[id[i][j]].x + 0.2;
    dfs(ex, ey);
    int tmp = 0;
    for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) C[tmp++].x = c[i][j];
    dft(C, 1); dft(D, 1); for (int i = 0; i < N; ++i) A[i] = C[i] * D[i]; dft(A, -1); for (int i = 0; i < N; ++i) A[i].x /= N;
    int ans = 0;
    for (int i = 1; i < n; ++i) for (int j = 1; j < m; ++j) ans += (int(A[id[i][j]].x+0.2) > 0);
    printf("%d", ans);
}