题意
真的想不到是(FFT)的题，用了一个晚上基本弄懂了。
首先我们要解决的是用一个小矩形在一个大矩形上匹配的问题，如果是一维的就是这道题。
现在是二维的，我们将每一行拆出来，按照第(1)行、第(2)行、...、第(n)行的顺序拼接在一起，拼出一个长为(n*m)的串，考虑在这上面解决问题。
我们先找到最小的包含舰队的矩形，将这个矩阵作为左上角的补成一个(n*m)的矩形，我们称为舰队矩形,我们将这个矩形也按照刚才的方式处理成一个串。
拿样例举个例子：
图：
....#
.o#.o
.o..o
..o..
最小的包含舰队的矩形：
o#.o
o..o
.o..
舰船矩形:
o#.o.
o..o.
.o...
.....
现在我们有两个串，一个是图的串，我们称为(s)，另一个是舰队矩形的串，我们称为(t)。
我们对这个两个串构建两个序列(a,b)。
(a)这个序列是对(s)构建的，其中：(a_i=[s_i=#])，即如果(i)这个点是障碍，那么(a_i=1)。
(b)这个序列是对(t)构建的，其中(b_i=[t_i=o])，即如果(i)这个点在舰队矩形中为船，那么(b_i=1)。它实际上表示的是各个舰船和最靠左上的舰船的相对位置，这样对于(s)中任意位置(x),用(b_{i})即可表示以(x)为左上角时(s_{x+i})处是否有舰船。
我们现在考虑一个位置(x)，我们要判断(x)是否能成为舰队矩形的左上角，即是否能将舰队移到这个位置。
如果(x)满足条件，当且仅当((sumlimits_{i=0}^{nm-x-1}a_{x+i}b_i)=0)，这表示不存在一个(i)满足(a_{x+i}=1&&b_i=1)，即每个船应该在的位置都没有障碍。
我们将(a)翻转过来变为(a')，那么上面的式子就变为：((sumlimits_{i+j=nm-x}a'_ib_j)=0)，它其实就是(sumlimits_{i+j=x}a'_ib_j)翻转一下，我们可以(FFT)快速求出。
现在我们求出了所有可以放上的点，但是有些点可能无法到达，我们再跑个(bfs)将这些无法到达的点排除就好了。
之后我们要求出有多少点能被舰队覆盖，现在我们知道了所有能到达的左上角，它对应的序列为(a)（如果(i)这个点能到且是合法的左上角，那么(a_i=1)），那么一个位置(x)能被覆盖当且仅当：((sumlimits_{i+j=x}a_ib_j)>0)即至少存在一个左端点(i)，且(i+j)这个位置有舰船，这个卷积就更裸了。
code:
#include<cstdio>
#include<cmath>
#include<map>
#include<queue>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
const int maxn=710;
const int maxm=2000010;
const int inf=1e9;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const double Pi=acos(-1.0);
const double eps=0.5;
int n,m,x1=inf,yy1=inf,x2,y2,ans;
char a[maxn][maxn];
bool vis[maxn][maxn];
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
return res*f;
}
struct cplx{double x,y;}A[maxm],B[maxm];
cplx operator+(cplx a,cplx b){return (cplx){a.x+b.x,a.y+b.y};}
cplx operator-(cplx a,cplx b){return (cplx){a.x-b.x,a.y-b.y};}
cplx operator*(cplx a,cplx b){return (cplx){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
int lim=1,len;
int pos[maxm];
inline void FFT(cplx* a,int op)
{
for(int i=0;i<lim;i++)if(i<pos[i])swap(a[i],a[pos[i]]);
for(int l=1;l<lim;l<<=1)
{
cplx wn=(cplx){cos(Pi/l),op*sin(Pi/l)};
for(int i=0;i<lim;i+=l<<1)
{
cplx w=(cplx){1,0};
for(int j=0;j<l;j++,w=w*wn)
{
cplx x=a[i+j],y=w*a[i+l+j];
a[i+j]=x+y;a[i+l+j]=x-y;
}
}
}
if(op==1)return;
for(int i=0;i<lim;i++)a[i].x/=lim;
}
void bfs(int sx,int sy)
{
queue<pii>q;
q.push(mkp(sx,sy));
vis[sx][sy]=0;
while(!q.empty())
{
pii now=q.front();q.pop();
int x=now.fir,y=now.sec;
A[(x-1)*m+y-1].x=1;
for(int i=0;i<4;i++)
{
int mx=x+dx[i],my=y+dy[i];
if(vis[mx][my])vis[mx][my]=0,q.push(mkp(mx,my));
}
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='o')x1=min(x1,i),yy1=min(yy1,j),x2=max(x2,i),y2=max(y2,j);
else if(a[i][j]=='#')A[n*m-(i-1)*m-j]=(cplx){1,0};
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='o')B[(i-x1)*m+j-yy1]=(cplx){1,0};
while(lim<n*m)lim<<=1,len++;
for(int i=0;i<lim;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(len-1));
FFT(A,1);FFT(B,1);
for(int i=0;i<lim;i++)A[i]=A[i]*B[i];
FFT(A,-1);
for(int i=1;i<=n-(x2-x1);i++)
for(int j=1;j<=m-(y2-yy1);j++)
if(A[n*m-(i-1)*m-j].x<eps)vis[i][j]=1;
for(int i=0;i<lim;i++)A[i]=(cplx){0,0};
bfs(x1,yy1);
FFT(A,1);
for(int i=0;i<lim;i++)A[i]=A[i]*B[i];
FFT(A,-1);
for(int i=0;i<n*m;i++)if(A[i].x>eps)ans++;
printf("%d",ans);
return 0;
}