Участник:ArthurSamuelyan/Bricks Falling When Hit
Материал из DISCOPAL
- ссылка на задачу https://leetcode.com/problems/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; } } };