Created
September 12, 2013 14:09
-
-
Save huangxf/6538018 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?xml version="1.0" encoding="UTF-8"?> | |
<module type="JAVA_MODULE" version="4"> | |
<component name="NewModuleRootManager" inherit-compiler-output="true"> | |
<exclude-output /> | |
<content url="file://$MODULE_DIR$"> | |
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" /> | |
</content> | |
<orderEntry type="jdk" jdkName="1.6" jdkType="JavaSDK" /> | |
<orderEntry type="sourceFolder" forTests="false" /> | |
<orderEntry type="module-library" exported=""> | |
<library> | |
<CLASSES> | |
<root url="jar://$MODULE_DIR$/textbooklib/algs4.jar!/" /> | |
<root url="jar://$MODULE_DIR$/textbooklib/stdlib.jar!/" /> | |
</CLASSES> | |
<JAVADOC /> | |
<SOURCES> | |
<root url="jar://$MODULE_DIR$/textbooklib/algs4.jar!/" /> | |
<root url="jar://$MODULE_DIR$/textbooklib/stdlib.jar!/" /> | |
</SOURCES> | |
</library> | |
</orderEntry> | |
</component> | |
</module> | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Created with IntelliJ IDEA. | |
* User: user | |
* Date: 13-9-6 | |
* Time: 上午1:14 | |
* To change this template use File | Settings | File Templates. | |
*/ | |
/**************************************************************************** | |
* Compilation: javac InteractivePercolationVisualizer.java | |
* Execution: java InteractivePercolationVisualizer N | |
* Dependencies: PercolationVisualizer.java Percolation.java | |
* StdDraw.java StdOut.java | |
* | |
* This program takes the grid size N as a command-line argument. | |
* Then, the user repeatedly clicks sites to open with the mouse. | |
* After each site is opened, it draws full sites in light blue, | |
* open sites (that aren't full) in white, and blocked sites in black. | |
* | |
****************************************************************************/ | |
public class InteractivePercolationVisualizer { | |
public static void main(String[] args) { | |
// N-by-N percolation system (read from command-line, default = 10) | |
int N = 10; | |
if (args.length == 1) N = Integer.parseInt(args[0]); | |
// repeatedly open site specified my mouse click and draw resulting system | |
StdOut.println(N); | |
StdDraw.show(0); | |
Percolation perc = new Percolation(N); | |
PercolationVisualizer.draw(perc, N); | |
StdDraw.show(0); | |
while (true) { | |
// detected mouse click | |
if (StdDraw.mousePressed()) { | |
// screen coordinates | |
double x = StdDraw.mouseX(); | |
double y = StdDraw.mouseY(); | |
// convert to row i, column j | |
int i = (int) (N - Math.floor(y)); | |
int j = (int) (1 + Math.floor(x)); | |
// open site (i, j) provided it's in bounds | |
if (i >= 1 && i <= N && j >= 1 && j <= N) { | |
if (!perc.isOpen(i, j)) { | |
StdOut.println(i + " " + j); | |
} | |
perc.open(i, j); | |
} | |
// draw N-by-N percolation system | |
StdDraw.show(0); | |
PercolationVisualizer.draw(perc, N); | |
} | |
StdDraw.show(20); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Created with IntelliJ IDEA. | |
* User: user | |
* Date: 13-9-6 | |
* Time: 上午2:28 | |
* To change this template use File | Settings | File Templates. | |
*/ | |
public class MyWightedQuickUnionUF extends WeightedQuickUnionUF{ | |
public MyWightedQuickUnionUF(int N) { | |
super(N); | |
} | |
public void union(int i,int j){ | |
super.union(i,j); | |
System.out.println("union("+i+","+j+")"); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Created with IntelliJ IDEA. | |
* User: user | |
* Date: 13-9-5 | |
* Time: 11:19 pm | |
* To change this template use File | Settings | File Templates. | |
*/ | |
public class Percolation { | |
private WeightedQuickUnionUF weightedQuickUnionUF; | |
private int[] gridFlag; | |
private int N; | |
/** | |
* create N-by-N grid, with all sites blocked | |
*/ | |
public Percolation(int N) { | |
this.N = N; | |
//define a N*N size array to represents N*N grids. | |
//In this case, the grid(i,j) is map to array[i*N+j-1] | |
//Additional, other two virtual sites are set in array which stored in array[N*N] and array[N*N+1] | |
//These two additional virtual sites represent top site and bottom site respectively | |
weightedQuickUnionUF = new WeightedQuickUnionUF (N*N + 2); | |
gridFlag = new int[N*N + 2]; | |
for (int i = 0; i < N*N + 2; i++) { | |
gridFlag[i] = 0; //0 represents blocked, 1 represents open | |
} | |
} | |
/** | |
* // open site (row i, column j) if it is not already | |
* | |
* @param i | |
* @param j | |
*/ | |
public void open(int i, int j) { | |
//Range check | |
if (i < 1 || i > N) { | |
throw new ArrayIndexOutOfBoundsException("row number is out of bound as " + i); | |
} | |
//Connect current site to its neighbours (four directions) | |
if (j < 1 || j > N) { | |
throw new ArrayIndexOutOfBoundsException("col number is out of bound as " + j); | |
} | |
if (i > 1 && (gridFlag[(i - 2) * N + j - 1] == 1 || gridFlag[(i - 2) * N + j - 1] == 2)) { | |
weightedQuickUnionUF.union((i - 1) * N + j - 1, (i - 2) * N + j - 1); //union to upper grid | |
} | |
if (i < N && (gridFlag[i * N + j - 1] == 1 || gridFlag[i * N + j - 1] == 2)) { | |
weightedQuickUnionUF.union((i - 1) * N + j - 1, i * N + j - 1); //union to lower grid | |
} | |
if (j < N && (gridFlag[(i - 1) * N + j] == 1 || gridFlag[(i - 1) * N + j] == 2)) { | |
weightedQuickUnionUF.union((i - 1) * N + j - 1, (i - 1) * N + j); //union to right grid | |
} | |
if (j > 1 && (gridFlag[(i - 1) * N + j - 2] == 1 || gridFlag[(i - 1) * N + j - 2] == 2)) { | |
weightedQuickUnionUF.union((i - 1) * N + j - 1, (i - 1) * N + j - 2); //union to left grid | |
} | |
gridFlag[(i - 1) * N + j - 1] = 1; //set grid as open | |
//If current site is in first row, make the top virtual site open and union current site to top virtual site. | |
if (i == 1){ | |
gridFlag[N*N] = 1; | |
weightedQuickUnionUF.union((i - 1) * N + j - 1, N * N); | |
} | |
//If current site is in last row, make the bottom virtual site open and union current site to bottom virtual site. | |
if (i == N && !this.percolates()){ | |
gridFlag[N*N+1] = 1; | |
}else if(i == N && this.percolates()){ //use this to handle backwash | |
gridFlag[N*N+1] = 1; | |
weightedQuickUnionUF.union((i - 1) * N + j - 1, N * N + 1); | |
} | |
// //scan all open grid and update necessary ones to full | |
// for (int x = 1; x <= N; x++) { | |
// for (int y = 1; y <= N; y++) { | |
// if (gridFlag[(x - 1) * N + y - 1] == 1) { | |
// if (isFull(x, y)) { | |
// gridFlag[(x - 1) * N + y - 1] = 2; //if grid is full open, set flag as full open | |
// } | |
// } | |
// } | |
// } | |
// if (isFull(i, j)) { | |
// gridFlag[(i - 1) * N + j - 1] = 2; //if grid is full open, set flag as full open | |
// } | |
} | |
/** | |
* // is site (row i, column j) open? | |
* | |
* @param i | |
* @param j | |
* @return | |
*/ | |
public boolean isOpen(int i, int j) { | |
if (i < 1 || j < 1 || i > N || j > N){ | |
throw new IndexOutOfBoundsException(); | |
} | |
if (gridFlag[(i - 1) * N + j - 1] == 1) { | |
return true; | |
} | |
return false; | |
} | |
/** | |
* // is site (row i, column j) full? | |
* | |
* @param i | |
* @param j | |
* @return | |
*/ | |
public boolean isFull(int i, int j) { | |
if (i < 1 || j < 1 || i > N || j > N){ | |
throw new IndexOutOfBoundsException(); | |
} | |
//if site is not open, it's must not full. | |
if (gridFlag[(i - 1) * N + j - 1] == 0) { | |
return false; | |
} | |
if(weightedQuickUnionUF.connected((i-1)*N+j-1,N*N) && gridFlag[N*N] == 1){ | |
return true; | |
} | |
// for (int k = 1; k <= N; k++) { | |
// //if current site is connected to any open site in first row, it's full open | |
// if (weightedQuickUnionUF.connected((i - 1) * N + j - 1, k - 1) && (gridFlag[k - 1] == 2||gridFlag[k - 1] == 1)) { | |
// gridFlag[(i - 1) * N + j - 1] = 2; | |
// return true; | |
// } | |
// } | |
return false; | |
} | |
/** | |
* // does the system percolate? | |
* | |
* @return | |
*/ | |
public boolean percolates() { | |
// for (int k = 0; k < N; k++) { | |
// if (gridFlag[N * N - N + k] == 2) { | |
// return true; | |
// } | |
// } | |
if(weightedQuickUnionUF.connected(N*N, N*N + 1) == true){ | |
return true; | |
} | |
return false; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
PK 羠(C牖白x 6 Percolation.java蚗KS鉌維�桁acc!R9,靚栰.U鋊騹蕘�K#<冬Q蛯皾�O鲗,Kbd/乀�X瓰烆~�`喑d1,笧繣汄_噔俗矯簋Z1y�廮P��嗭��煋 8 轆>��填�W犢<O�乻�x�樦<籗H甁e.貅黩b滘�T | |
~e2鴼�逤%��2~7�~+x4晃P琥`釔�騆哕聺漶y�} 核蕔�@d 冄p�帉下�(嶲�褜烹#~宕 �P宪鸳笭��G鹆8�鷡��at0耴廟��$�S,邮��捳賸替" | |
箴#3:=頜麁鈟槗c飭�觓p[?菧�S棤罟訣笌9��]樨b拢 (-$騥-紸o!题豌爕渍C1雒曛諹U艰und柒Xh-骣哏,尹灔珝u-鑼-���8钭2眆Ly巋Tj葜�!龄枺扪)�>崒淄摒[{瞒応�)錋P棅渆;忲悖嫷緊�:=)衧悈�bA\2菻駒嵺破�斸x[0�紽髙羉s��U5mD铥繘NMX4蹐褯!烂B鞅U!禞(世�嬞虿袟上⑷b鮱避�糖萙孫D俓)垉 | |
轥Jx=�z挚�藧HR�~X,严�hI*��b.塼"S齠0觰0���檀3嬯Gt漤[鑅凜�)庨$zN�@ | |
~剥钤:�壠Ue�+A脢育S罗�皨<莯蓷a�C�倆箩[I舃w 缨伌.晔OK愕r�堵慸lw8n���Rヵ鷄6�g`O鐎肕�d�")Rq赹�薎抄`E銣L窽�x8榞虒k歴�h{9 =雚�吊邾B`骰F悪�了@雁栔�W緑翦` �.L檥g6\蕵牾�3^ |W炘|s窮4U脲Z 1��B5y庛&�TQQ槞5譅k塊�m�橰伻樄;)掖n≮z柖 栶炛XX�螰场讲讷R{逶^鏼Sw�M嬶8\%^潱劢��|罨h楏}磇惵t;犀�瓑aM躸祝肱aC惺]-0\处v5瑮S雿]�Z熵=韶O蟔6釗d簮臊返|巺H矙�hc諟6v瓮局巩uojW縩G"�h#-娑[*$!v愑�J��宋�"兆c嚲鬤�~.p憣 9|f驇簰W螹暉厚瀞圖�媞�兙齰頰?镉|h蚻荰铯幊q蟣+灂瓁鎙�祸璁��萔弹浲テ@苜 銤88晏�k鎙持?<8W��]H镪輀匮U贡牨�慫)玩P�帰龞挰�M |82|瑕C�靊34x褪u�騭嘹\祴X^鶡�^O隹��羼PK +f(C��� � PercolationStats.java誛Ko跢���h@�)5H丠Q袵捼AK50|犎暩 _賋Zb��I嫟热1欳�懟簋ff圅htz#鴀0O�6\卲�E�\納�ハ�L�莀塯0}5~3~�\悠t鲢+肉b+?魭5r 娕Y刲$>饒�\1矕w軖Fjヶ镮�#顑yR逻L��筊瀿瘗�閜e傔戣 Ezvs譻癿咙T蓝h^�偵<R癑0�A� )呢# Z#�銫�\郔���?嵆\i3绩!=M繩�/wc謧徛~�崤啻7躩�)黰{jp噪�孟%.姮u H卅蜣綕�衺吞慺2鏾�k喂i�血i叕擸�溼忌@係嬩�y琔4)6!耲既斆�l氕DmQ纓迃峨9#rph\┼/ 邑�N啊芥磎23x鴬监��秅�紎 z鏑Ez-Z檿VL俰裒誑b}Xi�体DE�衆sk�嫖g��a5屿o旮�稳�煐 | |
E貉鵳�敖陶尻�O鶁氤Lg莯B$�^2�翄氨;,煴@�X妁犗儑庙嚔H�[�Y'8f桸v巭��q菺�=�嵧!倜�鬤讔]��~^唣[J立^�$l儉☉検�旚癮2�鰸t5祫揳諝恅*Iw�屟拰z*`猔Y �EpU⊥I;i | |
0�M'��y�茎S饭衼<V�⒊哩DU�N┌)xxu鞄腰O�U�;肹E鳗醈嫰VE谊�扩siQ&录:雓喙}�J�oLZ啠趕焄怇繽�-鵌(CR粮丿沠V豮巆���kI=嵃V!���挰8搡>H1q鏓邉鵀�魗鄜痪え駩饟瞘豣斩宎j�*踮5燔侯医簚р杇禀彭�蟨;缦芃砵[嚏醰慰�� ^�莵��_鈝菕a锭cO琫7L掓o頡�b�8舍栈粕焫��t嶯o&鮇c頥缬踶筅G袐�顓尖綅z{ 0n�C狲)碔A;�+%�Fc�g嚏+蝹僡q_[瑎��姈_唇肰8=凬�⒎.MP蛴袿m�龆騼�篨樯搡�>湷�]ロ:掷�皧 | |
;&�i YU1撝訌fMi蜎B宵]囋巎c稈/PK 羠(C牖白x 6 Percolation.javaPK +f(C��� � � PercolationStats.javaPK � c | |