目前最优解来给一个严格 $O(n^2)$ 的做法。

然而在这篇题解写到一半的时候被@$\text{\color{black}{l}\color{red}{rqcs}}$ 最坏 $O(n^3)$ 的代码薄纱了，所以我是次优解：（

解析

思路

总的思路还是分三步：

1. 预处理出每个空格到墙的最近距离 $dis_{x,y}$。
2. 广搜别告诉我你准备用深搜，看哪些位置可到达，并处理出每个可到达位置的机器人“半径” $walk_{x,y}$。变量名是赛时乱起的，不用在意。
3. 覆盖所有的“菱形”，并统计有多少个格子被覆盖。

接下来思考一些问题。如果你已经会了其他题解的 $O(n^2)$ 或 $O(n^2 \log n)$ 做法，可以直接跳到后面的实现部分。

一些问题

Q：为什么要预处理 $dis_{x,y}$？

A：机器人复制后会向四周扩张一格，使得机器人到墙的距离缩短一格，所以到达 $(x,y)$ 时机器人最多只能扩张 $dis_{x,y} - 1$ 次。预处理出来 $dis_{x,y}$ 之后，我们第二步的搜索会更加方便。

Q：如何判断一个位置是否可以到达？

A：考虑下一个位置 $(x,y)$，如果 $dis_{x,y} > \left\lfloor \frac{step - 1}{d}\right\rfloor$（其中 $step$ 为走到 $(x,y)$ 需要的步数），那么 $(x,y)$ 是可以走到的。

需要注意的一点是，当 $dis_{x,y} \times d = step$ 时，$(x,y)$ 这个位置是可以走到的，只是说刚走到这个位置就因为复制而坠机了，但这个位置依旧会造成贡献，所以右边应该是 $\left\lfloor \frac{step - 1}{d}\right\rfloor$ 而非 $\left\lfloor \frac{step}{d}\right\rfloor$。

Q：BFS 时一个点需不需要走多次？

A：不需要！

假如你在 $(x,y)$ 时，对于一个此时还没覆盖过的点 $(x',y')$，你需要走到更远的点去等到机器人复制之后再回来覆盖的话——

那你为什么不一开始就走到 $(x',y')$ 附近去把它覆盖掉呢？总不可能你直接走过去覆盖不到，复制之后反而能覆盖得到吧？

所以每个点我们搜一次就够了。用 BFS 可以直接做到 $O(n^2)$。

好了，接下来进入本篇题解的核心——实现部分。

实现

第一步

最直白的做法是使用广搜，将所有的墙加入队列后直接扩展，但是这么做常数好像有点大？

注意到对于一个格子 $(x,y)$，离它最近的墙只有四种情况：

1. 在左上方。
2. 在左下方。
3. 在右上方。
4. 在右下方。

对于左上方的情况又分三种：

1. 是距离 $(x - 1,y)$ 最近的墙。
2. 是距离 $(x,y - 1)$ 最近的墙。
3. 我自己就是墙。

所以对于每一个空地，我们可以直接递推：

$$dis_{x,y} = \min(dis_{x - 1,y},dis_{x,y - 1}) + 1$$

其余三种情况差不多，改一下式子和转移顺序即可。

实测比直接 BFS 快。

第二步

刚才我们可以递推是因为我们不需要考虑墙的阻挡带来的影响，但现在不行了，因为墙不能走，只能劲爆 BFS。

其实直接根据上面 $dis_{x,y} > \left\lfloor \frac{step - 1}{d}\right\rfloor$ 这个式子去转移就可以了，但是——

这个除法有点慢啊？

于是我采用了一种猎奇写法。具体地，先限定只走 $d - 1$ 步，等到准备走第 $d$ 步时，将一个变量 $limit$ 加一，并且把所有的第 $d$ 步的状态步数清零！

此时 $limit = \left\lfloor \frac{step}{d}\right\rfloor$，特判一下因为复制而坠机的情况即可。

第三步

预处理完 $walk$ 数组后，我们就只需要统计有多少个格子被覆盖就行了。

然而……对于每个由机器人组成的“菱形”，暴力覆盖的复杂度疑似和 $O(n^4)$ 同阶；用一维差分的复杂度也约为 $O(n^3)$；二维差分又不能很好的解决问题……

这时我们回顾一下第一步的过程：向四个方位拆贡献。

刚才我们可以递推是因为我们不需要考虑墙的阻挡带来的影响。

那现在不也一样吗？！

因为同一个位置覆盖多次对答案不会产生影响，所以我们尝试将菱形拆成四个部分去覆盖，即左上、左下、右上和右下。每个部分都是三角形。

以右下为例，在 $(x,y)$ 这个位置的三角形都是可以覆盖到往右下走 $walk_{x,y}$ 个格子的区域的。所以我们维护一个从当前位置往右下能覆盖到的最远距离 $r_{x,y}$。

还是三种情况：

1. $(x - 1,y)$ 或其更左上角的覆盖距离最远。
2. $(x,y - 1)$ 或其更左上角的覆盖距离最远。
3. $(x,y)$ 的覆盖距离最远。

所以：

$$r_{x,y} = \max(walk_{x,y},\max(r_{x - 1,y},r_{x,y - 1}) - 1)$$

剩下三种情况也差不多。最后统计有多少格子的 $\max{r_{x,y}} \geq 0$ 即可。

注意 $walk,dis,r$ 的初始值不能为 $0$，需要赋极值。（墙的 $dis$ 可以为 $0$。）

AC code

#include<bits/stdc++.h>
#define int1 int
#define N 1000
#define M 1000000
#define K 4
#define INF 1145141919
#define Getchar getchar
using namespace std;
int1 n,d,i,j,ans;
int1 dis[N + 5][N + 5];
int1 walk[N + 5][N + 5];
int1 r[N + 5][N + 5],rr[N + 5][N + 5];
bitset<N + 5> can[N + 5],vis[N + 5];
const int1 dx[K] = {1,-1,0,0},dy[K] = {0,0,1,-1};
struct qwq{
	int1 step,x,y;
};
struct que{
	int1 head,tail;
	qwq q[M + 5];
	que(){
		head = 1,tail = 0;
	}
	const qwq front(){
		return q[head];
	}
	void pop(){
		head++;
		return ;
	}
	void push(qwq x){
		q[++tail] = x;
		return ;
	}
	const bool size(){
		return (tail >= head);
	}
} solve;
inline const int1 read(){
	int1 f = 1,x = 0;
	char ch = Getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-'){
			f = -f;
		}
		ch = Getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = Getchar();
	}
	return f * x;
}
void uprint(const int1 x){
	if(x >= 10){
		uprint(x / 10);
	}
	putchar(x % 10 ^ 48);
	return ;
}
void print(int1 x){
	if(x < 0){
		x = -x;
		putchar('-');
	}
	return uprint(x);
}
void ps(const int1 x){
	print(x);
	putchar(' ');
	return ;
}
void pe(const int1 x){
	print(x);
	putchar('\n');
	return ;
}
int main(){
	n = read(),d = read();
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			char ch = Getchar();
			while(ch != 'S' && ch != '#' && ch != '.'){
				ch = Getchar();
			}
			if(ch != '#'){
				can[i][j] = 1;
				if(ch == 'S'){
					vis[i][j] = 1;
					solve.push(qwq{0,i,j});
				}
				dis[i][j] = INF;
			}
			walk[i][j] = rr[i][j] = -1;
		}
	}
	for(i = 2; i < n; i++){
		for(j = 2; j < n; j++){
			dis[i][j] = min(dis[i][j],min(dis[i - 1][j],dis[i][j - 1]) + 1);
		}
	}
	for(i = 2; i < n; i++){
		for(j = n - 1; j >= 2; j--){
			dis[i][j] = min(dis[i][j],min(dis[i - 1][j],dis[i][j + 1]) + 1);
		}
	}
	for(i = n - 1; i >= 2; i--){
		for(j = 2; j < n; j++){
			dis[i][j] = min(dis[i][j],min(dis[i + 1][j],dis[i][j - 1]) + 1);
		}
	}
	for(i = n - 1; i >= 2; i--){
		for(j = n - 1; j >= 2; j--){
			dis[i][j] = min(dis[i][j],min(dis[i + 1][j],dis[i][j + 1]) + 1);
		}
	}
	int1 limit = 0;
	do{
		for(i = solve.head; i <= solve.tail; i++){
			solve.q[i].step = 0;
		}
		while(solve.size()){
			qwq now = solve.front();
			if(now.step == d){
				break;
			}
			solve.pop();
			if(dis[now.x][now.y] <= limit){
				walk[now.x][now.y] = dis[now.x][now.y] - 1;
				continue;
			}
			walk[now.x][now.y] = limit;
			now.step++;
			for(i = 0; i < K; i++){
				int1 nx = now.x + dx[i],ny = now.y + dy[i];
				if(1 <= nx && nx <= n && 1 <= ny && ny <= n && !vis[nx][ny] && dis[nx][ny] > limit){
					vis[nx][ny] = 1;
					solve.push((qwq){now.step,nx,ny});
				}
			}
		}
		limit++;
	}while(solve.size());
	for(i = 2; i < n; i++){
		for(j = 2; j < n; j++){
			r[i][j] = max(walk[i][j],max(r[i - 1][j],r[i][j - 1]) - 1);
			rr[i][j] = max(rr[i][j],r[i][j]);
		}
	}
	for(i = 2; i < n; i++){
		for(j = n - 1; j >= 2; j--){
			r[i][j] = max(walk[i][j],max(r[i - 1][j],r[i][j + 1]) - 1);
			rr[i][j] = max(rr[i][j],r[i][j]);
		}
	}
	for(i = n - 1; i >= 2; i--){
		for(j = 2; j < n; j++){
			r[i][j] = max(walk[i][j],max(r[i + 1][j],r[i][j - 1]) - 1);
			rr[i][j] = max(rr[i][j],r[i][j]);
		}
	}
	for(i = n - 1; i >= 2; i--){
		for(j = n - 1; j >= 2; j--){
			r[i][j] = max(walk[i][j],max(r[i + 1][j],r[i][j + 1]) - 1);
			rr[i][j] = max(rr[i][j],r[i][j]);
		}
	}
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			if(rr[i][j] >= 0){
				ans++;
			}
		}
	}
	pe(ans);
	return 0;
}