一個點用坐標x,y)表示,如果兩個點在水平方向或垂直方向上相鄰,則兩個點屬於一個區域,即點1x1,y1),點2x2,y2)相鄰當且僅當x1==x2,|y1-y2|=1或者|x1-x2|=1,y1=y2。給定一些點,相鄰的點構成一個區域,求出k個區域所能擁有的最大點數。k不大於區域數)。
可用並查集解決,一個區域表示為一個並查集,兩個區域相鄰時,合並這兩個並查集。同時記錄並查集中的點數目。
初始時,每個點為一個並查集。
對x坐標相同、y坐標相差為1的點,合並它們所在的並查集,合並時需要判斷兩個點是否位於同一個集合。合並時需要先找到各自集合的根節點,然後讓其中一個根節點指向另一個根節點完成合並。
對y坐標相同、x坐標相差為1的點,合並它們所在的並查集。
當所有相鄰點進行了合並操作之後,對並查集點數目從大到小排序,取前K個值的總和作為結果輸出。
解題源碼,請訪問:http://www.51ojr.com/report/full/44