程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> POJ 1838 解題報告

POJ 1838 解題報告

編輯:關於C語言

問題翻譯


      一個點用坐標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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved