Update Readme.md

wisdompeak · web-flow · commit 8fc6ad3e4e9f · 2021-04-15T00:22:47.000-07:00
diff --git a/DFS/803.Bricks-Falling-When-Hit/Readme.md b/DFS/803.Bricks-Falling-When-Hit/Readme.md
@@ -1,5 +1,7 @@
 ### 803.Bricks-Falling-When-Hit
 
+#### &#35299;&#27861;1&#65306;DFS
+
 &#36825;&#39064;&#21643;&#30475;&#19978;&#21435;&#24456;&#38590;&#65292;&#20294;&#23454;&#38469;&#19978;&#29992;&ldquo;&#26102;&#20809;&#20498;&#27969;&rdquo;&#30340;&#24819;&#27861;&#23601;&#24456;&#26041;&#20415;&#12290;
 
 &#20551;&#24819;&#22312;&#25152;&#26377;&#30340;erasure&#23436;&#25104;&#20043;&#21518;&#65292;&#36825;&#20123;&#30742;&#22359;&#26377;&#20123;&#19982;top&#30456;&#36830;&#65288;&#25104;&#20026;&#22823;&#38470;&#65289;&#65289;&#65292;&#26377;&#20123;&#21017;&#26159;&#23396;&#31435;&#30340;&#23707;&#23679;&#12290;&#25105;&#20204;&#32771;&#23519;&#26368;&#21518;&#19968;&#27425;&#25277;&#25481;&#30340;&#30742;&#22359;&#65292;&#22914;&#26524;&ldquo;&#22797;&#21407;&rdquo;&#23427;&#33021;&#20351;&#24471;&#19968;&#20123;&#23396;&#31435;&#30340;&#23707;&#23679;&#19982;&#22823;&#38470;&#30456;&#36830;&#30340;&#35805;&#65292;&#37027;&#20040;&#36825;&#20123;&#23707;&#23679;&#30340;&#38754;&#31215;S&#65292;&#20854;&#23454;&#23601;&#26159;&#26368;&#21518;&#19968;&#27425;erasure&#25152;&#36896;&#25104;&#30742;&#22359;&#25481;&#33853;&#30340;&#25968;&#37327;&#12290;OK&#65292;&#23601;&#31639;&#36825;&#27425;&ldquo;&#22797;&#21407;&rdquo;&#19981;&#33021;&#20351;&#24471;&#20219;&#20309;&#23707;&#23679;&#19982;&#22823;&#38470;&#30456;&#36830;&#65292;&#20294;&#20063;&#26377;&#21487;&#33021;&#20250;&#20351;&#24471;&#19968;&#37096;&#20998;&#23707;&#23679;&#20043;&#38388;&#30456;&#36830;&#65292;&#36825;&#26679;&#19979;&#19968;&#27425;&ldquo;&#22797;&#21407;&rdquo;&#30340;&#26102;&#20505;&#23601;&#26377;&#21487;&#33021;&#20351;&#24471;&#36825;&#19968;&#22359;&#26356;&#22823;&#30340;&#23707;&#23679;&#19982;&#22823;&#38470;&#30456;&#36830;&#12290;&#20197;&#27492;&#26041;&#27861;&#19981;&#20572;&#22320;&#24448;&#22238;&#36861;&#28335;&#19978;&#21435;&#12290;
@@ -14,5 +16,10 @@
 
 4.&#20381;&#27425;&#31867;&#25512;&#22788;&#29702;&#25152;&#26377;&#30340;erasure&#12290;
 
+#### &#35299;&#27861;2&#65306;Union Find
+
+&#21516;&#26679;&#26159;&#26102;&#20809;&#20498;&#27969;&#30340;&#24819;&#27861;&#12290;&#23558;&#25152;&#26377;erasure&#20043;&#21518;&#30340;&#22320;&#22270;&#36890;&#36807;Union Find&#24471;&#21040;&#21508;&#20010;&#32852;&#36890;&#21306;&#22495;&#12290;&#29305;&#21035;&#27880;&#24847;&#65292;Union&#30340;&#26102;&#20505;&#19981;&#20165;&#35201;&#26356;&#26032;&#27599;&#20010;&#26684;&#23376;&#30340;Father&#65292;&#36824;&#35201;&#26356;&#26032;&#27599;&#20010;&#26684;&#23376;&#30340;Father&#30340;Size&#65292;&#20063;&#23601;&#26159;&#35813;&#32852;&#36890;&#22359;&#30340;&#22823;&#23567;&#12290;
+
+&#36870;&#24207;&#22788;&#29702;&#27599;&#19968;&#20010;erasure&#30340;&#26102;&#20505;&#65292;&#26597;&#30475;&#35813;&#26684;&#23376;(x,y)&#30456;&#37051;&#30340;&#22235;&#20010;&#20301;&#32622;&#12290;&#22914;&#26524;&#26377;&#19968;&#20010;&#30456;&#37051;&#30340;&#20301;&#32622;(i,j)&#30340;Father&#26159;&#31532;&#19968;&#34892;&#65292;&#25110;&#32773;(x,y)&#26412;&#36523;&#23601;&#26159;&#31532;&#19968;&#34892;&#65292;&#37027;&#20040;&#23427;&#30340;&#25830;&#38500;&#23601;&#19968;&#23450;&#20250;&#23548;&#33268;&#30742;&#22359;&#30340;&#25481;&#33853;&#12290;&#25481;&#33853;&#30340;&#20010;&#25968;&#23601;&#26159;&#19982;(x,y)&#30456;&#37051;&#30340;&#12289;Father&#19981;&#26159;&#31532;&#19968;&#34892;&#30340;&#32852;&#36890;&#22359;&#30340;&#22823;&#23567;&#30340;&#24635;&#21644;&#12290;
 
 [Leetcode Link](https://leetcode.com/problems/bricks-falling-when-hit)

-Original file line number
+Diff line change
@@ @@ -1,5 +1,7 @@ @@
 ### 803.Bricks-Falling-When-Hit
 +#### 解法1：DFS
++
 这题咋看上去很难，但实际上用“时光倒流”的想法就很方便。
 假想在所有的erasure完成之后，这些砖块有些与top相连（成为大陆）），有些则是孤立的岛屿。我们考察最后一次抽掉的砖块，如果“复原”它能使得一些孤立的岛屿与大陆相连的话，那么这些岛屿的面积S，其实就是最后一次erasure所造成砖块掉落的数量。OK，就算这次“复原”不能使得任何岛屿与大陆相连，但也有可能会使得一部分岛屿之间相连，这样下一次“复原”的时候就有可能使得这一块更大的岛屿与大陆相连。以此方法不停地往回追溯上去。
 .依次类推处理所有的erasure。
 +#### 解法2：Union Find
++
 +同样是时光倒流的想法。将所有erasure之后的地图通过Union Find得到各个联通区域。特别注意，Union的时候不仅要更新每个格子的Father，还要更新每个格子的Father的Size，也就是该联通块的大小。
++
 +逆序处理每一个erasure的时候，查看该格子(x,y)相邻的四个位置。如果有一个相邻的位置(i,j)的Father是第一行，或者(x,y)本身就是第一行，那么它的擦除就一定会导致砖块的掉落。掉落的个数就是与(x,y)相邻的、Father不是第一行的联通块的大小的总和。
 [Leetcode Link](https://leetcode.com/problems/bricks-falling-when-hit)