# Участник:ArthurSamuelyan/Bricks Falling When Hit

Перейти к: навигация, поиск
```class Solution {
public:

vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {

markBricksInit(grid);

vector<int> fallenBricks;
for (unsigned k = 0; k < hits.size(); k++) {

unsigned hit_i = (unsigned)(hits[k][0]);
unsigned hit_j = (unsigned)(hits[k][1]);
int hit_val = grid[hit_i][hit_j];
int fallen = 0;

if (hit_val) {
grid[hit_i][hit_j] = 0;
unsigned n_i, n_j;
vector<vector<vector<vector<unsigned>>>> clusters;
for (unsigned d = 0; d < 4; d++) {
if (checkNeighbour(grid, d, hit_i, hit_j, n_i, n_j) > hit_val) {
vector<vector<unsigned>> clusterFrontInit({{n_i, n_j}});
clusters.push_back({vector<vector<unsigned>>(), vector<vector<unsigned>>()});
markCluster(grid, hit_val, clusterFrontInit, clusters.back()[0], clusters.back()[1]);
}
}
for (unsigned cIter = 0; cIter < clusters.size(); cIter++) {
if (clusters[cIter][1].size()) {
/* Cluster will not fall,
* but requires recalculation */

restoreMarks(grid, clusters[cIter][1]);

} else {
fallen += clusters[cIter][0].size();
for (unsigned iter = 0; iter < clusters[cIter][0].size(); iter++) {
unsigned fall_i = clusters[cIter][0][iter][0];
unsigned fall_j = clusters[cIter][0][iter][1];
grid[fall_i][fall_j] = 0;
}
}
}
}

fallenBricks.push_back(fallen);
}
return fallenBricks;
}

private:

void markBricksInit(vector<vector<int>>& grid) {

/* Keep the 0 string '1's.
* All the other bricks set 'unmarked' - '-1': */
for (unsigned i = 1; i < grid.size(); i++) {
for (unsigned j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == 1) grid[i][j] = -1;
}
}

vector<vector<unsigned>> prev, next;
for (unsigned j = 0; j < grid[0].size(); j++) {
if (grid[0][j] == 1) prev.push_back((vector<unsigned>){0, j});
}

unsigned k = 2;
do {
next.clear();

for (unsigned iter = 0; iter < prev.size(); iter++) {
unsigned i = prev[iter][0];
unsigned j = prev[iter][1];
unsigned n_i, n_j;
for (unsigned d = 0; d < 4; d++) {
if (checkNeighbour(grid, d, i, j, n_i, n_j) == -1) {
grid[n_i][n_j] = k;
next.push_back((vector<unsigned>){n_i, n_j});
}
}
}

prev = next;
k++;
} while(next.size());
}

int checkNeighbour(vector<vector<int>>& grid,
unsigned d,
unsigned i,
unsigned j,
unsigned& n_i,
unsigned& n_j) {
d = d % 4;
n_i = i;
n_j = j;
switch (d) {
case 0:
if (i > 0) { n_i = i - 1; } else { return 0; }
break;
case 1:
if (j > 0) { n_j = j - 1; } else { return 0; }
break;
case 2:
if (i < grid.size() - 1) { n_i = i + 1; } else { return 0; }
break;
case 3:
if (j < grid[n_i].size() - 1) { n_j = j + 1; } else { return 0; }
break;
default:
{}
break;
}
return grid[n_i][n_j];
}

/* marks (*= -1) all the attached items,
* whose value is greater, than 'borderVal'.
* + adds their coords to 'cluster'
* for a better further processing. */
void markCluster(vector<vector<int>>& grid,
int borderVal,
const vector<vector<unsigned>>& clusterFrontInit,
vector<vector<unsigned>>& cluster,
vector<vector<unsigned>>& border)
{
vector<vector<unsigned>> prev = clusterFrontInit;
vector<vector<unsigned>> next;

for (unsigned iter = 0; iter < prev.size(); iter++) {
grid[prev[iter][0]][prev[iter][1]] *= -1;
}

while (prev.size()) {
next.clear();
for (unsigned iter = 0; iter < prev.size(); iter++) {
cluster.push_back(prev[iter]);

unsigned i = prev[iter][0];
unsigned j = prev[iter][1];
unsigned n_i, n_j;

for (unsigned d = 0; d < 4; d++) {
int n_val = checkNeighbour(grid, d, i, j, n_i, n_j);
if (n_val > borderVal) {
grid[n_i][n_j] *= -1;
next.push_back((vector<unsigned>){n_i, n_j});
} else if (n_val == borderVal) {
border.push_back((vector<unsigned>){i, j});
}
}
}
prev = next;
}
}

void restoreMarks(vector<vector<int>>& grid,
const vector<vector<unsigned>>& frontInit)
{
vector<vector<unsigned>> prev = frontInit;
vector<vector<unsigned>> next;

/*  */
for (unsigned iter = 0; iter < prev.size(); iter++) {
unsigned i = prev[iter][0];
unsigned j = prev[iter][1];
grid[i][j] *= -1;
}

while (prev.size()) {
next.clear();
for (unsigned iter = 0; iter < prev.size(); iter++) {
unsigned i = prev[iter][0];
unsigned j = prev[iter][1];
unsigned n_i, n_j;

for (unsigned d = 0; d < 4; d++) {
int n_val = checkNeighbour(grid, d, i, j, n_i, n_j);
if (n_val < 0) {
grid[n_i][n_j] = grid[i][j] + 1;
next.push_back((vector<unsigned>){n_i, n_j});
}
}
}
prev = next;
}
}

};```