被FFT的空间卡了半天 后来发现根本不用开那么大...

首先可以把包含舰艇的那个小矩形找出来 将它一行一行连接成一个串T 其中舰艇位置为1其他位置为0 将大矩形也连成串S 其中礁石为1其他为0

两个串匹配起来如果某一位两个串是1和1 则礁石与舰艇会在同一位置不可能到达 那么这个匹配所对应的图中的位置就不成立

因为要确定每个位置可以想到将T翻转后做FFT后每一位(每一位代表了一个小矩形的匹配情况)上结果是0就可以匹配上 为1不成立 选出为0的 做一遍BFS 求出可以到达的位置

可以发现可行的状态里面会有重复的空地 所以再做一次FFT T串为小矩形的正序串 S串为BFS后的可行装状态串 之后对结果的数组中实数个数计数就是答案咧

#include<bits/stdc++.h>

#define bug(x) cout<<(#x)<<" "<<(x)<<endl

#define ll long long

#define mod 1000000007

#define inf 2e9

#define PI acos(-1.0)

#define pii pair<int,int>

#define fi first

#define se second

#define mk make_pair

using namespace std;

const int N=1e6+5

const int MXN=7e2+5;

struct cp {

	double x,y;

	cp(double _x=0,double _y=0) { x=_x,y=_y;}

}A[N],B[N];

cp operator + (cp x,cp y){cp z;z.x=x.x+y.x;z.y=x.y+y.y;return z;}

cp operator - (cp x,cp y){cp z;z.x=x.x-y.x;z.y=x.y-y.y;return z;}

cp operator * (cp x,cp y){cp z;z.x=x.x*y.x-x.y*y.y;z.y=x.y*y.x+x.x*y.y;return z;}

int ans,up=inf,dn,lf=inf,rt,W,H,all,k,len,M,n,m,r[N],T[N];

queue<pii >q;

char a[MXN][MXN];

bool vis[N],v[N];

void init(){

	for(int i=0;i<n;i++) for(int j=0;j<m;j++){

		if(a[i][j]=='#') B[i*m+j]=cp(1,0);

		else if(a[i][j]=='o'){

			up=min(up,i),dn=max(dn,i);

			lf=min(lf,j),rt=max(rt,j);

		}

	}

	for(int i=up;i<=dn;i++) for(int j=lf;j<=rt;j++) if(a[i][j]=='o')T[(i-up)*m+j-lf]=1;

	W=rt-lf+1,H=dn-up+1,len=(H-1)*m+W;

}

void FFT(cp *x,int f){

	for(int i=0;i<M;i++) if(r[i]>i) swap(x[r[i]],x[i]);

	for(int i=1;i<M;i<<=1){

		cp wn(cos(PI/i),f*sin(PI/i));

		for(int j=0;j<M;j+=i<<1){

			cp w=1;

			for(int k=0;k<i;k++,w=w*wn){

				cp a=x[j+k],b=w*x[j+k+i];

				x[j+k]=a+b,x[j+k+i]=a-b;

			}

		}

	}

	if(f==-1) for(int i=0;i<M;i++) x[i].x/=M;

}

void work(){

	q.push(mk(dn,rt));

	while(!q.empty()){

		int x=q.front().fi,y=q.front().se;q.pop();

		if(x<0||x>=n||y<0||y>=m) continue;

		int z=x*m+y;

		if(!v[z]||vis[z]) continue;

		vis[z]=1;

		q.push(mk(x+1,y)),q.push(mk(x-1,y)),q.push(mk(x,y-1)),q.push(mk(x,y+1));

	}

}

int main(){

#ifdef Devil_Gary

	freopen("in.txt","r",stdin);

#endif

/*	freopen("sailing.in","r",stdin);

	freopen("sailing.out","w",stdout);*/

	cin>>n>>m,all=n*m;

	for(int i=0;i<n;i++) scanf("%s",a[i]);

	init();

	for(M=1;M<=all;M<<=1,k++);

	for(int i=1;i<M;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(k-1));

  	for(int i=0;i<len;i++) if(T[i]) A[len-i-1]=1;

	FFT(A,1),FFT(B,1);

	for(int i=0;i<M;i++) A[i]=A[i]*B[i];

	FFT(A,-1);

	for(int i=H-1;i<n;i++) for(int j=W-1;j<m;j++)

		if(A[i*m+j].x<0.5) v[i*m+j]=1;

	work();

  	for(int i=0;i<M;i++) A[i]=T[i];

  	for(int i=0;i<M;i++) B[i]=vis[i];

	FFT(A,1),FFT(B,1);

	for(int i=0;i<M;i++) A[i]=A[i]*B[i];

	FFT(A,-1);

	for(int i=0;i<M;i++) if(A[i].x>0.5) ans++;

	return printf("%d\n",ans),0;

}