USACO 2020 December Contest, Gold Problem 1. Replication
USACO 2020 December Contest, Gold Problem 1. Replication
The ill-fated result of watching too many "do it yourself" engineering videos on the web, Farmer John has accidentally released a self-replicating robot on his farm!
The farm can be represented by an N×NN×N grid (3≤N≤10003≤N≤1000) where each grid cell is either empty or filled with rock, and all border squares are filled with rock. Some non-rock cells are designated as possible starting locations for the robot.
Farmer John initially places the robot at one of the possible starting positions. In every hour that follows, all copies of the robot move in one coordinated mass in the same direction, either north, south, east, or west. After every DD hours (1≤D≤1091≤D≤109), every copy of the robot replicates --- a robot at cell (x,y)(x,y) that replicates creates new copies in cells (x+1,y)(x+1,y), (x−1,y)(x−1,y), (x,y+1)(x,y+1), and (x,y−1)(x,y−1); the original robot remains at (x,y)(x,y). Over time, multiple robots might come to occupy the same cell.
If moving or replicating would cause any of the robots to move into a rock, then all robots shut down immediately. Note that this implies that the robots must eventually shut down, due to the border of the farm being rock.
Help the cows figure out the number of empty squares that could potentially at some point in time hold a robot.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains two space-separated integers NN and DD. The next NN lines of input each contain NN characters. Each character is one of '.', 'S', or '#'. '.' and 'S' both represent empty cells, with 'S' denoting a possible starting position for the robot. '#' denotes a rock.All characters in the first and last row and first and last column are '#'.
OUTPUT FORMAT (print output to the terminal / stdout):
An integer counting the number of cells that could at some point in time hold a robot.
SAMPLE INPUT:
10 1 ########## #........# #S.......# #........# ########## #S....S..# ########## ########## ########## ##########
SAMPLE OUTPUT:
15
In the following diagrams, x's denote robots.
Locations that could be occupied by robots:
########## #xxx.....# #xxxx....# #xxx.....# ########## #xx..xxx.# ########## ########## ########## ##########
One possible sequence of events could be as follows:
- FJ places the robot at the upper-left-most starting position.
- The robot moves one unit to the right.
- The robot replicates.
- All robots move one unit to the right.
- Another replication would cause a copy of the robot to move into a rock, so the process terminates.
########## ########## ########## ########## #........# #........# #.x......# #..x.....# #x.......# #.x......# #xxx.....# #.xxx....# #........# #........# #.x......# #..x.....# ########## -> ########## -> ########## -> ########## #........# #........# #........# #........# ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ##########
SAMPLE INPUT:
10 2 ########## #.#......# #.#......# #S.......# #.#......# #.#......# ########## ########## ########## ##########
SAMPLE OUTPUT:
28
Locations that could be occupied by robots:
########## #x#.xxx..# #x#xxxxx.# #xxxxxxxx# #x#xxxxx.# #x#.xxx..# ########## ########## ########## ##########
SAMPLE INPUT:
10 2 ########## #.S#.....# #..#.....# #S.......# #..#.....# #..#.....# ########## ########## ########## ##########
SAMPLE OUTPUT:
10
Locations that could be occupied by robots:
########## #xx#.....# #xx#.....# #xxx.....# #xx#.....# #x.#.....# ########## ########## ########## ##########
SCORING:
- Test cases 4-5 satisfy D=109D=109.
- Test cases 6-8 satisfy D=1D=1.
- Test cases 9-12 satisfy N≤100N≤100.
- Test cases 13-20 satisfy no additional constraints.
Problem credits: Benjamin Qi
USACO 2020 December Contest, Gold Problem 1. Replication 题解(翰林国际教育提供，仅供参考)
[/hide]
(Analysis by Spencer Compton)
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 ii replications all cells within distance ii 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 ii replications within distance ii 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]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 r1,c1r1,c1 to a cell r2,c2r2,c2 for hour tt (0-indexed), then this condition is met if t−1<D×rock_dist[r1][c1]t−1<D×rock_dist[r1][c1] and t≤D×rock_dist[r2][c2]t≤D×rock_dist[r2][c2].
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]−1rock_dist[r][c]−1 times.
Thus, our final condition for whether a cell r,cr,c can ever have a robot is if there is some cell r′,c′r′,c′ where a center robot can be at r′,c′r′,c′ and |r−r′|+|c−c′|≤rock_dist[r′][c′]−1|r−r′|+|c−c′|≤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]centers[i] that contains all cells r,cr,c that can have a center robot and rock_dist[r][c]=irock_dist[r][c]=i. We can do our BFS in stages from n/2n/2 (because this is the maximum possible rock_distrock_dist) to 00, and at the end of each stage ii add all cells in centers[i]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;
}
[/hide]
国际竞赛真题资料-点击免费领取！
美高学分项目重磅来袭！立即了解
