Go ahead and look up the set!

The title

Make bricks

There is a binary grid of m x N, where 1 represents the brick and 0 represents the blank. The premise of tile stability (will not fall) is that a tile is directly connected to the top of the grid, or at least one adjacent (one of 4 directions) tile stability will not fall when giving you an array hits, which is needed to eliminate the tile position in turn. Whenever a block at hits[I] = (Rowi, coli) is eliminated, the block (if present) disappears, and other blocks may fall as a result of the elimination operation. Once a brick falls, it immediately disappears from the grid (i.e., it does not land on other stable bricks). Return an array result, where result[I] represents the number of tiles dropped for the ith elimination operation. Note that elimination may point to a blank position where there are no bricks, and if that happens, no bricks fall. Example 1: input grid = [,0,0,0 [1], [1,1,1,0]], output hits = [[1, 0]] : [2] : grid for: [,0,0,0 [1], [1,1,1,0]] eliminate (1, 0) bold bricks, get the grid: The [[1,0,0,0] [0,1,1,0]] two thick bricks are no longer stable because they are no longer attached to the top or adjacent to another stable brick, so they will fall. The grid is obtained: [[1,0,0,0], [0,0,0]] therefore, the result is [2]. Example 2: input grid = [,0,0,0 [1], [1,1,0,0]], hits = [[1, 1], [1, 0]] output: [0, 0] explain: grid for: ,1,0,0,0,0,0 [[1], [1]] eliminate (1, 1) enlarging the bricks, get the grid: [,0,0,0 [1], [1,0,0,0]] the rest of the brick is stable, so will not fall off. The grid remains the same: [[1,0,0,0], [1,0,0,0]] then eliminate the bold bricks at (1,0) to get the grid: [[1,0,0,0], [0,0,0]] the remaining bricks are still stable, so no bricks fall. Therefore, the result is [0,0].Copy the code

Analysis of the

My mind a bit of a wandering at the beginning, from the positive consideration, think through and look set to each component to maintain a number of connections, roof and then abort bricks when the number of connections minus one, and then in the traversal components to search the number of connections to 0 to do statistics, but doing so more write more complicated code, finally gave up, the official of reverse thinking.

The title and dismantling

Positive and dismantling

1. There is a matrix storing several components, marked as 1 means there is a link here, marked as 0 means there is no link here;

2, start from the roof, if you can go to a certain component, the component and the roof is connected, will not fall;

3, each time a knock action, check how many components lost the link with the roof, return the number;

In short, the problem is these three steps, and from the point of view of the problem, it’s a process of constantly disassembling the connected tree, each time you hit it, you have to split the original tree, and see how many components of the original tree are left.

However, the main ability to merge a set is merge and lookup, so splitting is not something that data structures excel at. But if you think about it the other way around, and we do all the taps and then go back and undo the original tree step by step, that’s a merge operation, and you get the connectivity judgment domain that sets are good at.

Let’s reassemble the problem with this idea

Reverse dismantled

1. There is a matrix storing several components, marked as 1 means there is a link here, marked as 0 means there is no link here;

2, start from the roof, if you can go to a certain component, the component and the roof is connected, will not fall;

3, each time in the matrix for a bonding operation, check the bonding, how many components are linked to the roof because of this bonding.

When you reverse engineer it, it becomes a lot clearer.

So let’s go ahead and analyze the steps

Analysis steps

1. All points in the whole matrix can be regarded as a tree linked to the roof, and there is only one tree in the collection of parallel search.

2. Each point in the matrix is a component, and an additional component is defined to mark the roof.

3. There are two pre-merger operations: 1) If it is in the first row, it needs to be merged with the roof; 2) The connected components are combined

4. Add a connection number attribute to the component that identifies the number of components with the current component as the root node.

5. After each merging operation, the number of components increased by the roof as the root node represents the number of components added through this bonding action.

The problem solving steps

1. Customize and look up the set, and add the total number of components with the current component as the root node

2. Copy a matrix and perform all hit operations to get a final matrix, which is the reverse initial matrix.

3. Initialize and look up the set, and merge the reverse initial matrix

4. Glue one connection point at a time, judge whether merge operation is required and execute it.

5. Obtain the total number of components linked to the roof before and after the merger, make the difference and record the results.

Code implementation

And look up set builds

Class HitBricksUnionFind {// Store connection component protected int[] id; Protected int count; WeightArr [] weightArr; weightArr [] weightArr; Public HitBricksUnionFind(int n) {this.count = n; This. id = new int[n]; // Initialize an array containing full components this.id = new int[n]; for (int i = 0; i < n; I ++) {// The initial value of each component points to its own id[I] = I; } weightArr = new int[n]; For (int I = 0; int I = 0; i < weightArr.length; i++) { weightArr[i] = 1; }} void union(int p, int q) {int pId = find(p); Int qId = find(q); If (pId == qId) return; If (weightArr[pId] < weightArr[qId]) {id[pId] = qId; weightArr[qId] += weightArr[pId]; } else { id[qId] = pId; weightArr[pId] += weightArr[qId]; } // Each merge reduces a different component group count--; } int find(int p) { if (p == id[p]) return p; Id [p] = find(id[p]); // Find (id[p]); return id[p]; ** @param p * @return */ int getWeight(int p) {int root = find(p); return weightArr[root]; }}Copy the code

Algorithm code

class Solution { private static int rowCount = 0; private static int colCount = 0; public static int[] hitBricks(int[][] grid, int[][] hits) { rowCount = grid.length; colCount = grid[0].length; Int [][] tenet = new int[rowCount][colCount]; for (int i = 0; i < tenet.length; i++) { for (int j = 0; j < tenet[i].length; j++) { tenet[i][j] = grid[i][j]; For (int[] hit: hits) {tenet[hit[0]][hit[1]] = 0; Int size = rowCount * colCount; int size = rowCount * colCount; HitBricksUnionFind uf = new HitBricksUnionFind(size + 1); Int I = 0; for (int I = 0; i < tenet[0].length; i++) { if (tenet[0][i] == 1) { uf.union(getUfIndex(0, i), size); Start with the second row and merge the link components; 1) Connected to the left side; For (int I = 1; i < tenet.length; i++) { for (int j = 0; j < tenet[i].length; J ++) {if (tenet[I][j] == 1) {// if (tenet[I][j] == 1) {// if (tenet[I - 1][j] == 1) {// If (tenet[I - 1][j] == 1) {// If (tenet[I - 1][j] == 1) {// If (tenet[I - 1][j] == 1) { getUfIndex(i - 1, j)); } if (j > 0 && tenet[I][J-1] == 1) {// Union (getUfIndex(I, j), getUfIndex(I, j-1)); }}}} / / three execution gluing operation, the adhesive is the hit of the reverse operation, operation will be hits flashbacks traversal / / 3.1 defines four directions int [] [] dir = new int [] [] {{1, 0}, {0, 1}, {1, 0}, {0, 1}}; int[] res = new int[hits.length]; for (int k = hits.length - 1; k >= 0; k--) { int[] hit = hits[k]; int i = hit[0]; int j = hit[1]; If (grid[I][j] == 0) continue; if (grid[I][j] == 0) continue; int totalCount = uf.getWeight(size); if (i == 0) { uf.union(j, size); } for (int[] ints: dir) {int m = ints[0]; int n = ints[1]; int x = i + m; int y = j + n; if (inArea(x, y) && tenet[x][y] == 1) { uf.union(getUfIndex(x, y), getUfIndex(i, j)); } } int totalCountNew = uf.getWeight(size); Res [k] = math.max (0, totalCountnew-totalcount-1); [j] = 1; // } return res; } private static int getUfIndex(int x, int y) { return x * colCount + y; } private static boolean inArea(int x, int y) { return x >= 0 && x < rowCount && y >= 0 && y < colCount; }}Copy the code