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

Ссылки сюда (1) →

• ссылка на задачу 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;
    }
  }
 
};