Replication

#include <bits/stdc++.h>
using namespace std;
 
struct State {
	int i, j;
	int distance;
};
 
int main() {
	int n, d;
	cin >> n >> d;
 
	vector<vector<char>> grid(n, vector<char>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { cin >> grid[i][j]; }
	}
 
	// BFS con las rocas como fuentes
	// Calcula la distancia de cada celda a la roca más cercana
	vector<vector<int>> rock_dist(n, vector<int>(n));
	queue<State> queue;
	for (int i = 0; i < n; i++) {
		fill(rock_dist[i].begin(), rock_dist[i].end(), -1);
		for (int j = 0; j < n; j++) {
			if (grid[i][j] == '#') { queue.push(State{i, j, 0}); }
		}
	}
	while (!queue.empty()) {
		State state = queue.front();
		queue.pop();
 
		// Saltamos si la posición está fuera de los límites
		if (state.i < 0 || state.i >= n || state.j < 0 || state.j >= n) { continue; }
		// Saltamos si la celda ya fue visitada
		if (rock_dist[state.i][state.j] != -1) { continue; }
		rock_dist[state.i][state.j] = state.distance;
 
		for (int i = -1; i <= 1; i += 2) {
			queue.push(State{state.i + i, state.j, state.distance + 1});
			queue.push(State{state.i, state.j + i, state.distance + 1});
		}
	}
 
	// BFS desde las fuentes
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] == 'S') { queue.push(State{i, j, 0}); }
		}
	}
 
	/*
	 * Representamos un clúster por la posición del robot central y el tamaño
	 * Una celda está "visitada" si la ocupa un robot central
	 * "vis" guarda el tamaño del clúster que visita cada celda
	 * Si la celda nunca se visita, su valor será -1
	 */
	vector<vector<int>> vis(n, vector<int>(n));
	for (int i = 0; i < n; i++) { fill(vis[i].begin(), vis[i].end(), -1); }
 
	while (!queue.empty()) {
		State state = queue.front();
		queue.pop();
 
		int size = (state.distance - 1) / d;
 
		// Saltamos si la posición está fuera de los límites
		if (state.i < 0 || state.i >= n || state.j < 0 || state.j >= n) { continue; }
		// Saltamos si la celda ya fue visitada
		if (vis[state.i][state.j] != -1) { continue; }
		// Saltamos si el clúster chocará con una roca
		if (rock_dist[state.i][state.j] <= size) { continue; }
 
		vis[state.i][state.j] = size;
		// Actualizamos el tamaño del clúster de robots
		size = (state.distance) / d;
		// Revisamos si el nuevo tamaño choca con rocas
		if (rock_dist[state.i][state.j] <= size) { continue; }
		// Si no, continuamos el BFS
		vis[state.i][state.j] = size;
 
		for (int i = -1; i <= 1; i += 2) {
			queue.push(State{state.i + i, state.j, state.distance + 1});
			queue.push(State{state.i, state.j + i, state.distance + 1});
		}
	}
 
	// BFS multi-fuente para expandir desde todos los centros usando su radio
	vector<vector<int>> cover(n, vector<int>(n, -1));
	while (!queue.empty()) queue.pop();
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (vis[i][j] >= 0) queue.push(State{i, j, vis[i][j]});
		}
	}
 
	while (!queue.empty()) {
		State s = queue.front();
		queue.pop();
 
		if (s.i < 0 || s.i >= n || s.j < 0 || s.j >= n) continue;
		if (grid[s.i][s.j] == '#') continue;
		if (s.distance <= cover[s.i][s.j]) continue;
 
		cover[s.i][s.j] = s.distance;
 
		if (s.distance > 0) {
			queue.push(State{s.i + 1, s.j, s.distance - 1});
			queue.push(State{s.i - 1, s.j, s.distance - 1});
			queue.push(State{s.i, s.j + 1, s.distance - 1});
			queue.push(State{s.i, s.j - 1, s.distance - 1});
		}
	}
 
	// Marcamos las celdas cubiertas como 'x'
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (cover[i][j] >= 0) grid[i][j] = 'x';
		}
	}
 
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { ans += (grid[i][j] == 'x') ? 1 : 0; }
	}
 
	cout << ans << endl;
}

import java.io.*;
import java.util.*;
 
public class Replication {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
 
		int n = sc.nextInt();
		int d = sc.nextInt();
 
		char[][] grid = new char[n][n];
		for (int i = 0; i < n; i++) {
			String temp = sc.next();
			for (int j = 0; j < n; j++) { grid[i][j] = temp.charAt(j); }
		}
 
		// BFS con las rocas como fuentes
		// Calcula la distancia de cada celda a la roca más cercana
		int[][] rockDist = new int[n][n];
		Queue<State> queue = new LinkedList<>();
		for (int i = 0; i < n; i++) {
			Arrays.fill(rockDist[i], -1);
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == '#') { queue.add(new State(i, j, 0)); }
			}
		}
		while (!queue.isEmpty()) {
			State state = queue.remove();
 
			// Saltamos si la posición está fuera de los límites
			if (state.i < 0 || state.i >= n || state.j < 0 || state.j >= n) {
				continue;
			}
			// Saltamos si la celda ya fue visitada
			if (rockDist[state.i][state.j] != -1) { continue; }
			rockDist[state.i][state.j] = state.distance;
 
			for (int i = -1; i <= 1; i += 2) {
				queue.add(new State(state.i + i, state.j, state.distance + 1));
				queue.add(new State(state.i, state.j + i, state.distance + 1));
			}
		}
 
		// BFS desde las fuentes
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == 'S') { queue.add(new State(i, j, 0)); }
			}
		}
		// Representamos un clúster por la posición del robot central y el tamaño
		// Una celda está "visitada" si la ocupa un robot central
		// "vis" guarda el tamaño del clúster que visita cada celda
		// Si la celda nunca se visita, su valor será -1
		int[][] vis = new int[n][n];
		for (int i = 0; i < n; i++) Arrays.fill(vis[i], -1);
		while (!queue.isEmpty()) {
			State state = queue.remove();
			int size = (state.distance - 1) / d;
 
			// Saltamos si la posición está fuera de los límites
			if (state.i < 0 || state.i >= n || state.j < 0 || state.j >= n) {
				continue;
			}
			// Saltamos si la celda ya fue visitada
			if (vis[state.i][state.j] != -1) continue;
			// Saltamos si el clúster chocará con una roca
			if (rockDist[state.i][state.j] <= size) continue;
 
			vis[state.i][state.j] = size;
			// Actualizamos el tamaño del clúster de robots
			size = (state.distance) / d;
			// Revisamos si el nuevo tamaño choca con rocas
			if (rockDist[state.i][state.j] <= size) { continue; }
			// Si no, continuamos el BFS
			vis[state.i][state.j] = size;
 
			for (int i = -1; i <= 1; i += 2) {
				queue.add(new State(state.i + i, state.j, state.distance + 1));
				queue.add(new State(state.i, state.j + i, state.distance + 1));
			}
		}
 
		// Ponemos la celda en 'x' si un robot puede ocuparla
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int di = 0; di <= vis[i][j]; di++) {
					for (int dj = 0; dj <= vis[i][j] - di; dj++) {
						grid[i + di][j + dj] = 'x';
						grid[i - di][j + dj] = 'x';
						grid[i + di][j - dj] = 'x';
						grid[i - di][j - dj] = 'x';
					}
				}
			}
		}
 
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) { ans += (grid[i][j] == 'x') ? 1 : 0; }
		}
 
		out.println(ans);
		out.close();
	}
 
	static class State {
		int i, j;
		int distance;
 
		State(int i, int j, int distance) {
			this.i = i;
			this.j = j;
			this.distance = distance;
		}
	}
}