First, we make an observation about what our swarm of robots will look like as they replicate. As the robots replicate, they would take the following shape:

..... ..... ..X.. ..... ..X.. .XXX. ..X.. -> .XXX. -> XXXXX ..... ..X.. .XXX. ..... ..... ..X..

More intuitively, we can view the shape of our swarm as some cell with a center robot, and after $i$ replications all cells within distance $i$ of the center will have robots in the swarm.

If a cell can have a robot, then we know there is either a way to have a center robot at that cell, or there is a way to have a center robot with $i$ replications within distance $i$ of the cell.

This motivates us to figure out which cells can have a center robot, and the maximum number of replications it can have. To accomplish this, we intend to make a modified BFS from the source cells to figure out which cells can have a center robot. In order to accomplish this, however, we will need to know if at some time, the swarm is too big to go to a certain cell (and thus moving there would cause robots to go into rocks).

To help with this, we will calculate the distance from every cell to its nearest rock cell. We can do this with a BFS where all the rocks are sources. We call the distance from each cell to a rock $rock\_dist[r][c]$. Now, we use a modified BFS to determine which cells could contain a center robot. As we expand our BFS, we only move to a cell if it would not cause any robots to crash into rocks. If we are moving from a cell $r_1,c_1$ to a cell $r_2,c_2$ for hour $t$ (0-indexed), then this condition is met if $t-1 < D \times rock\_dist[r_1][c_1]$ and $t \le D \times rock\_dist[r_2][c_2]$.

Armed with what cells can be center robots, we observe that we can stay at said cell until the swarm has replicated a total of $rock\_dist[r][c]-1$ times.

Thus, our final condition for whether a cell $r,c$ can ever have a robot is if there is some cell $r',c'$ where a center robot can be at $r',c'$ and $|r-r'|+|c-c'| \le rock\_dist[r'][c']-1$. To calculate this, we again utilize a modified BFS. One such way of accomplishing this is having a set $centers[i]$ that contains all cells $r,c$ that can have a center robot and $rock\_dist[r][c]=i$. We can do our BFS in stages from $n/2$ (because this is the maximum possible $rock\_dist$) to $0$, and at the end of each stage $i$ add all cells in $centers[i]$ as sources. A cell will then be reached by our modified BFS exactly if it satisfies our condition, meaning we can determine the cells that can have robots.

#include <bits/stdc++.h> using namespace std; typedef long long ll; int dr[4] = {-1,1,0,0}; int dc[4] = {0,0,-1,1}; int main(){ int n; ll d; cin >> n >> d; bool empty[n][n]; vector<pair<int, int> > starts; vector<pair<int, int> > rocks; int dist_rock[n][n]; int dist_source[n][n]; bool ans[n][n]; for(int i = 0; i<n; i++){ string s; cin >> s; for(int j = 0; j<n; j++){ if(s[j]=='#'){ empty[i][j] = false; rocks.push_back(make_pair(i,j)); } else{ empty[i][j] = true; } if(s[j]=='S'){ starts.push_back(make_pair(i,j)); } dist_rock[i][j] = -1; dist_source[i][j] = -1; ans[i][j] = false; } } // First, we calculate distance of everything to a rock vector<pair<int, int> > bfs_list; for(int i = 0; i<rocks.size(); i++){ bfs_list.push_back(rocks[i]); dist_rock[rocks[i].first][rocks[i].second] = 0; } for(int i = 0; i<bfs_list.size(); i++){ pair<int, int> now = bfs_list[i]; for(int j = 0; j<4; j++){ pair<int, int> to = make_pair(now.first+dr[j],now.second+dc[j]); if(!(to.first>=0 && to.first<n && to.second>=0 && to.second<n)){ continue; } if(dist_rock[to.first][to.second]!=-1){ continue; } int to_dist = dist_rock[now.first][now.second] + 1; dist_rock[to.first][to.second] = to_dist; bfs_list.push_back(to); } } // Then, we do a BFS from the sources bfs_list.clear(); for(int i = 0; i<starts.size(); i++){ bfs_list.push_back(starts[i]); dist_source[starts[i].first][starts[i].second] = 0; } // centers[i] will store all empty cells i that our center // can reach, and who are distance i+1 from a rock // (meaning they can replicate i times) vector<pair<int, int> > centers[n*n]; for(int i = 0; i<bfs_list.size(); i++){ pair<int, int> now = bfs_list[i]; ans[now.first][now.second] = true; int now_dist = dist_source[now.first][now.second]; centers[dist_rock[now.first][now.second]-1].push_back(now); // Do not continue if replicating would force robots to rocks if(now_dist>=d*dist_rock[now.first][now.second]){ continue; } for(int j = 0; j<4; j++){ pair<int, int> to = make_pair(now.first+dr[j],now.second+dc[j]); if(!(to.first>=0 && to.first<n && to.second>=0 && to.second<n)){ continue; } if(dist_source[to.first][to.second]!=-1){ continue; } if(!empty[to.first][to.second]){ continue; } int to_dist = now_dist + 1; // Do not move if it would force robots to rocks if(to_dist > d*dist_rock[to.first][to.second]){ continue; } dist_source[to.first][to.second] = to_dist; bfs_list.push_back(to); } } // Do a modified BFS such that we reach every cell where // there is some other cell in centers[z] and the distance // between the two is <=z vector<pair<int, int> > next_stage; for(int i = n*n-1; i>=0; i--){ swap(bfs_list,next_stage); next_stage.clear(); for(int j = 0; j<bfs_list.size(); j++){ pair<int, int> now = bfs_list[j]; for(int k = 0; k<4; k++){ pair<int, int> to = make_pair(now.first+dr[k],now.second+dc[k]); if(!(to.first>=0 && to.first<n && to.second>=0 && to.second<n)){ continue; } if(ans[to.first][to.second]){ continue; } if(!empty[to.first][to.second]){ continue; } ans[to.first][to.second] = true; next_stage.push_back(to); } } for(int j = 0; j<centers[i].size(); j++){ next_stage.push_back(centers[i][j]); } } int tot = 0; for(int i = 0; i<n; i++){ for(int j = 0; j<n; j++){ if(ans[i][j]){ tot++; } } } cout << tot << endl; }