|
8 | 8 |
|
9 | 9 | publicclass_694 { |
10 | 10 | publicstaticclassSolution1 { |
11 | | -/** |
12 | | - * My original idea: |
13 | | - * my not fully working yet: the equals() and hashcode() methods need to be refined |
14 | | - * because HashSet is not really filtering the islands wiht the same shape. |
15 | | - */ |
16 | | -classQuadrilateral { |
17 | | -int[]topLeft; |
18 | | -int[]bottomLeft; |
19 | | -int[]topRight; |
20 | | -int[]bottomRight; |
21 | | -intarea; |
22 | | - |
23 | | -publicQuadrilateral(inti,intj) { |
24 | | -this.area =0; |
25 | | -this.topLeft =newint[]{i,j}; |
26 | | -this.topRight =newint[]{i,j}; |
27 | | -this.bottomLeft =newint[]{i,j}; |
28 | | -this.bottomRight =newint[]{i,j}; |
29 | | - } |
30 | | - |
31 | | -@Override |
32 | | -publicbooleanequals(Objecto) { |
33 | | -if (this ==o) { |
34 | | -returntrue; |
35 | | - } |
36 | | -if (!(oinstanceofQuadrilateral)) { |
37 | | -returnfalse; |
38 | | - } |
39 | | - |
40 | | -Quadrilateralthat = (Quadrilateral)o; |
41 | | -returnthis.area ==that.area &&checkDistance(that); |
42 | | - } |
43 | | - |
44 | | -privatebooleancheckDistance(Quadrilateralthat) { |
45 | | -intthisTop =computeDistance(this.topLeft,this.topRight); |
46 | | -intthatTop =computeDistance(that.topLeft,that.topRight); |
47 | | -if (thisTop !=thatTop) { |
48 | | -returnfalse; |
49 | | - } |
50 | | -intthisRight =computeDistance(this.topRight,this.bottomRight); |
51 | | -intthatRight =computeDistance(that.topRight,that.bottomRight); |
52 | | -if (thisRight !=thatRight) { |
53 | | -returnfalse; |
54 | | - } |
55 | | -intthisBottom =computeDistance(this.bottomRight,this.bottomLeft); |
56 | | -intthatBottom =computeDistance(that.bottomRight,that.bottomLeft); |
57 | | -if (thisBottom !=thatBottom) { |
58 | | -returnfalse; |
59 | | - } |
60 | | -intthisLeft =computeDistance(this.bottomLeft,this.topLeft); |
61 | | -intthatLeft =computeDistance(that.bottomLeft,that.topLeft); |
62 | | -returnthisLeft ==thatLeft; |
63 | | - } |
64 | | - |
65 | | -privateintcomputeDistance(int[]A,int[]B) { |
66 | | -return (int) (Math.pow(A[0] -B[0],2) +Math.pow(A[1] -B[1],2)); |
67 | | - } |
68 | | - |
69 | | -@Override |
70 | | -publicinthashCode() { |
71 | | -returnarea +computeDistance(this.topLeft,this.topRight) +computeDistance(this.topRight,this.bottomRight) |
72 | | - +computeDistance(this.bottomRight,this.bottomLeft) +computeDistance(this.bottomLeft,this.topLeft); |
73 | | - } |
74 | | - |
75 | | -publicvoidaddPoint(inti,intj) { |
76 | | -//todo: check wether this point (i,j) is in the range, if not, expand the range |
77 | | -if (i ==topRight[0]) { |
78 | | -topRight[1] =Math.max(topRight[1],j); |
79 | | - } |
80 | | -if (j ==topRight[1]) { |
81 | | -topRight[0] =Math.min(topRight[1],i); |
82 | | - } |
83 | | -if (i ==topLeft[0]) { |
84 | | -topLeft[1] =Math.min(topLeft[1],j); |
85 | | - } |
86 | | -if (j ==topLeft[1]) { |
87 | | -topLeft[0] =Math.min(topLeft[0],i); |
88 | | - } |
89 | | -if (i ==bottomLeft[0]) { |
90 | | -bottomLeft[1] =Math.min(bottomLeft[1],j); |
91 | | - } |
92 | | -if (j ==bottomLeft[1]) { |
93 | | -bottomLeft[0] =Math.max(bottomLeft[0],i); |
94 | | - } |
95 | | -if (j ==bottomRight[1]) { |
96 | | -bottomRight[0] =Math.max(bottomRight[0],i); |
97 | | - } |
98 | | -if (i ==bottomRight[0]) { |
99 | | -bottomRight[1] =Math.max(bottomRight[1],j); |
100 | | - } |
101 | | - } |
102 | | - |
103 | | -publicvoidaddArea() { |
104 | | -this.area++; |
105 | | - } |
106 | | - } |
107 | | - |
108 | | -publicintnumDistinctIslands(int[][]grid) { |
109 | | -Set<Quadrilateral>set =newHashSet<>(); |
110 | | -intm =grid.length; |
111 | | -intn =grid[0].length; |
112 | | -for (inti =0;i <m;i++) { |
113 | | -for (intj =0;j <n;j++) { |
114 | | -if (grid[i][j] ==1) { |
115 | | -Quadrilateralquadrilateral =dfs(grid,i,j,m,n,newQuadrilateral(i,j)); |
116 | | -set.add(quadrilateral); |
117 | | - } |
118 | | - } |
119 | | - } |
120 | | -returnset.size(); |
121 | | - } |
122 | | - |
123 | | -privateQuadrilateraldfs(int[][]grid,inti,intj,intm,intn,Quadrilateralquadrilateral) { |
124 | | -if (i <0 ||j <0 ||i >=m ||j >=n ||grid[i][j] ==0) { |
125 | | -returnquadrilateral; |
126 | | - } |
127 | | -grid[i][j] =0; |
128 | | -quadrilateral.addPoint(i,j); |
129 | | -quadrilateral.addArea(); |
130 | | -quadrilateral =dfs(grid,i +1,j,m,n,quadrilateral); |
131 | | -quadrilateral =dfs(grid,i -1,j,m,n,quadrilateral); |
132 | | -quadrilateral =dfs(grid,i,j +1,m,n,quadrilateral); |
133 | | -quadrilateral =dfs(grid,i,j -1,m,n,quadrilateral); |
134 | | -returnquadrilateral; |
135 | | - } |
136 | | - } |
137 | | - |
138 | | -publicstaticclassSolution2 { |
139 | 11 | int[][]directions =newint[][]{ |
140 | 12 | {0,1}, |
141 | 13 | {1,0}, |
|