首页 > 代码库 > 海岛问题之Java实现
海岛问题之Java实现
问题描述：
You will be given a map of Soteholm as an N×M grid. Each square in the grid has a side length of 1 km and is either water or land. Your goal is to compute the total length of sea coast of all islands. Sea coast is all borders between land and sea, and sea is any water connected to an edge of the map only through water. Two squares are connected if they share an edge. You may assume that the map is surrounded by sea. Lakes and islands
in lakes are not contributing to the sea coast.
Figure 1:
Gray squares are land and white squares are water. The thick black line is the sea coast. This example corresponds to Sample Input 1.
Input
The first line of the input contains two space separated integers N and M where 1 ≤ N, M ≤ 1000. The following N lines each contain a string of length M consisting of only zeros and ones. Zero means water and one means land.
Input
The first line of the input contains two space separated integers N and M where 1 ≤ N, M ≤ 1000. The following N lines each contain a string of length M consisting of only zeros and ones. Zero means water and one means land.
Output
Output one line with one integer, the total length of the coast in km.
Sample Input 1
5 6
011110
010110
111000
000010
000000
Sample Output 1
20
算法简析：
该问题的关键就是如何区分海洋和湖泊。所求的长度即为陆地和海洋相邻的边的长度，即海岸线长度。
如何区分呢？ 我们看最边上的有水的地方必为海洋。 如果一个水快可以通过连续查找相邻水域，相邻水域中若有任一边缘水域块，即整块水域为海洋。
否则整块水域其为湖泊。
代码实现：
1 import java.util.HashMap; 2 import java.util.Map; 3 4 import javax.swing.text.html.HTMLDocument.Iterator; 5 6 7 public class LandCount { 8 9 10 public static void main (String argv[]){ 11 12 int[][] m; int leng=0; 13 m= new int[6][]; 14 for(int i=0;i<6;i++) 15 m[i]=new int[6]; 16 for(int i=0;i<6;i++){ 17 for(int j=0;j<6;j++){ 18 m[i][j]=0; 19 } 20 } 21 m[0][1]=1;m[0][2]=1;m[0][3]=1;m[0][4]=1; 22 m[1][1]=1;m[1][3]=1;m[1][4]=1; 23 m[2][0]=1;m[2][1]=1;m[2][2]=1; 24 m[3][4]=1; 25 for(int i=0;i<6;i++){ 26 for(int j=0;j<6;j++){ 27 System.out.print(" "+m[i][j]); 28 } 29 System.out.println(); 30 } 31 for(int i=0;i<=5;i++){ 32 for(int j=0;j<=5;j++){ 33 //System.out.println("i j m[i][j] "+i+j+m[i][j]); 34 if(m[i][j]==0){ 35 System.out.println(".........."+i+j); 36 check(m,i,j); 37 /*for(int q=0;q<6;q++){ 38 for(int w=0;w<6;w++){ 39 System.out.print(" "+m[q][w]); 40 } 41 System.out.println(); 42 }*/ 43 44 } 45 46 } 47 48 } 49 for(int i=0;i<6;i++){ 50 for(int j=0;j<6;j++){ 51 System.out.print(" "+m[i][j]); 52 53 } 54 System.out.println(); 55 } 56 for(int i=0;i<5;i++){ 57 for(int j=0;j<5;j++){ 58 if(m[i][j]==1){ 59 60 if(i==0||i==5) leng++; 61 if(j==0||j==5) leng++; 62 if(i>=1){ 63 if(m[i-1][j]==2) 64 leng++; 65 } 66 if(i+1<6){ 67 if(m[i+1][j]==2) 68 leng++; 69 } 70 if(j>=1){ 71 if(m[i][j-1]==2) 72 leng++; 73 } 74 if(j+1<6){ 75 if(m[i][j+1]==2) 76 leng++; 77 78 } 79 } 80 } 81 } 82 System.out.println("边界线:"+leng); 83 } 84 85 86 public static int checkTwo(kv[] s, int num, int u, int v){ 87 int i=0; 88 for(int p=0;p<num;p++){ 89 90 if(s[p].x==u&&s[p].y==v){ 91 i=1; break; 92 } 93 94 95 } 96 97 return i; 98 } 99 public static void check(int[][] l, int i, int j){100 101 102 103 kv [] s=new kv[36];104 for(int x=0;x<36;x++){105 106 s[x]=new kv();107 //System.out.print(s[x].x);108 //System.out.print(s[x].y);109 } 110 System.out.println();111 s[0].x=i;112 s[0].y=j;113 int num=1; int bz=0;114 for(int m=0;m<num;m++){ 115 int u=s[m].x;116 int v=s[m].y;117 System.out.print(u);118 System.out.println(v);119 if(u>=1){120 if(l[u-1][v]==0){ 121 122 if(checkTwo(s,num,u-1,v)==0){123 124 s[num].x=u-1;125 s[num].y=v;126 if(u-1==0||v==0||u-1==5||v==5)127 bz++;128 num++; 129 } 130 }131 }132 //System.out.println("num:"+num);133 if(u+1<=5){134 if(l[u+1][v]==0){135 136 if(checkTwo(s,num,u+1,v)==0){137 138 s[num].x=u+1;139 s[num].y=v;140 if(u+1==0||v==0||u+1==5||v==5)141 bz++;142 num++; 143 }144 }145 }146 //System.out.println("num:"+num);147 if(v>=1){148 if(l[u][v-1]==0){149 150 if(checkTwo(s,num,u,v-1)==0){151 152 s[num].x=u;153 s[num].y=v-1;154 if(u==0||v-1==0||u==5||v-1==5)155 bz++;156 num++; 157 }158 }159 }160 //System.out.println("num:"+num);161 if(v+1<=5){162 if(l[u][v+1]==0){163 164 if(checkTwo(s,num,u,v+1)==0){ 165 s[num].x=u;166 s[num].y=v+1;167 if(u==0||v+1==0||u==5||v+1==5)168 bz++;169 num++; 170 }171 }172 } 173 // System.out.println("num:"+num);174 }175 //System.out.println("num:"+num+"bz"+bz);176 if(bz>=1){177 System.out.println("They are 海洋："+num+"块！！！");178 for(int t=0;t<num;t++){179 int s_r=s[t].x;180 int s_l=s[t].y;181 l[s_r][s_l]=2;182 //System.out.println("chang"+s_r+s_l+l[s_r][s_l]);183 184 }185 186 }187 else188 System.out.println("They are 湖泊："+num+"块！！！");189 190 }191 192 193 194 static class kv{195 196 public int x;197 198 public int y;199 200 public kv(){201 this.x=10;202 this.y=10;203 204 }205 }206 }
有其引发出一小游戏： 即类似扫雷，在水域上随意添加陆地，然后计算海洋个数，湖泊个数和陆地边界线长度。
1 import java.awt.*; 2 import java.awt.event.ActionEvent; 3 import java.awt.event.ActionListener; 4 5 import javax.swing.*; 6 import javax.swing.*; 7 8 public class Haidao extends JFrame { 9 10 JButton random,clear,check; 11 JTextField Checkout; 12 ls[] B_ui; 13 public Haidao() { 14 15 random=new JButton("Random"); 16 clear=new JButton("Clear"); 17 check=new JButton("Check"); 18 B_ui=new ls[100]; 19 Checkout = new JTextField(20); 20 check.addActionListener(new ConcludeAction(B_ui,Checkout)); 21 clear.addActionListener(new ClearAction(B_ui)); 22 for(int i=0;i<100;i++){ 23 24 B_ui[i]= new ls(0); 25 B_ui[i].Button.addActionListener(new ChangeAction(B_ui[i])); 26 } 27 28 JPanel container1 = new JPanel(); 29 container1.setLayout(new GridLayout(1,4,5,5)); 30 JPanel container2 = new JPanel(); 31 container2.setLayout(new GridLayout(10,10,1,1)); 32 container1.setSize(600, 800); 33 container1.setSize(600, 100); 34 for(int i=0;i<100;i++){ 35 36 container2.add(B_ui[i].Button); 37 } 38 container1.add(random); 39 container1.add(clear); 40 container1.add(check); 41 container1.add(Checkout); 42 setLayout(new GridLayout(2,1,10,10)); 43 getContentPane().add(container2); 44 getContentPane().add(container1); 45 setVisible(true); 46 } 47 public class ChangeAction implements ActionListener { 48 public ls buttoni; 49 public void actionPerformed(ActionEvent e) { 50 buttoni.x=(buttoni.x+1)%2; 51 if(buttoni.x==1) 52 buttoni.Button.setBackground(Color.green); 53 if(buttoni.x==0) 54 buttoni.Button.setBackground(Color.white); 55 } 56 public ChangeAction(ls button) { 57 buttoni=button; 58 } 59 } 60 public class ConcludeAction implements ActionListener { 61 public JTextField textC; 62 public ls[] buttons; 63 public String Out; 64 public String huOut; 65 public String haiOut; 66 public int huid=0; 67 public int haiid=0; 68 public void actionPerformed(ActionEvent e) { 69 70 int[][] m; int leng=0;int BuiN=0; 71 m= new int[10][]; 72 for(int i=0;i<10;i++) 73 m[i]=new int[10]; 74 for(int i=0;i<10;i++){ 75 for(int j=0;j<10;j++){ 76 m[i][j]=buttons[BuiN].x; 77 System.out.print(m[i][j]); 78 BuiN++; 79 } 80 System.out.println(); 81 } 82 for(int i=0;i<10;i++){ 83 for(int j=0;j<10;j++){ 84 if(m[i][j]==0){ 85 check(m,i,j,Out); 86 } 87 } 88 } 89 BuiN=0; 90 for(int i=0;i<10;i++){ 91 for(int j=0;j<10;j++){ 92 buttons[BuiN].x=m[i][j]; 93 buttons[BuiN].setColour(); 94 BuiN++; 95 } 96 } 97 for(int i=0;i<=9;i++){ 98 for(int j=0;j<=9;j++){ 99 if(m[i][j]==1){ 100 101 if(i==0||i==9) leng++;102 if(j==0||j==9) leng++;103 if(i>=1){104 if(m[i-1][j]==2)105 leng++;106 } 107 if(i+1<=9){108 if(m[i+1][j]==2)109 leng++;110 }111 if(j>=1){112 if(m[i][j-1]==2)113 leng++;114 }115 if(j+1<=9){116 if(m[i][j+1]==2)117 leng++;118 119 }120 }121 }122 }123 124 Out=haiOut+huOut;125 Out=Out+"边界线length:"+leng;126 textC.setText(Out);127 Out="";128 haiOut="";129 huOut="";130 huid=0;131 haiid=0;132 //Out=Out+"边界线length:"+leng;133 134 } 135 public ConcludeAction(ls[] button,JTextField textfile) {136 buttons=button;137 textC=textfile;138 this.Out="";139 this.haiOut="";140 this.huOut="";141 }142 public int checkTwo(kv[] s, int num, int u, int v){143 int i=0;144 for(int p=0;p<num;p++){145 if(s[p].x==u&&s[p].y==v){146 i=1; break;147 }148 }149 150 return i;151 }152 public void check(int[][] l, int i, int j,String Out){153 154 kv [] s=new kv[100];155 for(int x=0;x<100;x++){156 157 s[x]=new kv();158 159 } 160 System.out.println();161 s[0].x=i;162 s[0].y=j;163 int num=1; int bz=0;164 for(int m=0;m<num;m++){ 165 int u=s[m].x;166 int v=s[m].y;167 System.out.print(u);168 System.out.println(v);169 if(u>=1){170 if(l[u-1][v]==0){ 171 172 if(checkTwo(s,num,u-1,v)==0){173 174 s[num].x=u-1;175 s[num].y=v;176 if(u-1==0||v==0||u-1==9||v==9)177 bz++;178 num++; 179 } 180 }181 }182 if(u+1<=9){183 if(l[u+1][v]==0){184 185 if(checkTwo(s,num,u+1,v)==0){186 187 s[num].x=u+1;188 s[num].y=v;189 if(u+1==0||v==0||u+1==9||v==9)190 bz++;191 num++; 192 }193 }194 }195 if(v>=1){196 if(l[u][v-1]==0){197 198 if(checkTwo(s,num,u,v-1)==0){199 200 s[num].x=u;201 s[num].y=v-1;202 if(u==0||v-1==0||u==9||v-1==9)203 bz++;204 num++; 205 }206 }207 }208 if(v+1<=9){209 if(l[u][v+1]==0){210 211 if(checkTwo(s,num,u,v+1)==0){ 212 s[num].x=u;213 s[num].y=v+1;214 if(u==0||v+1==0||u==9||v+1==9)215 bz++;216 num++; 217 }218 }219 } 220 }221 if(bz>=1){222 haiid++;223 haiOut=haiOut+"海洋"+haiid+"号: 面积为"+num+"！ ";224 System.out.println("海洋"+haiid+"号："+num+"块！！！");225 for(int t=0;t<num;t++){226 int s_r=s[t].x;227 int s_l=s[t].y;228 buttons[10*s_r+s_l].setColour();229 buttons[10*s_r+s_l].Button.setLabel(""+haiid); 230 Font font=new Font("楷体",Font.PLAIN,24); 231 buttons[10*s_r+s_l].Button.setFont(font);232 buttons[10*s_r+s_l].Button.setForeground(Color.blue); 233 //buttons[10*s_r+s_l].Button.234 l[s_r][s_l]=2;235 } 236 }237 else{238 huid++;239 huOut=huOut+"湖泊"+huid+"号："+num+"块！！！"+"\r";240 System.out.println("湖泊"+huid+"号: 面积为"+num+"！ ");241 for(int t=0;t<num;t++){242 int s_r=s[t].x;243 int s_l=s[t].y;244 buttons[10*s_r+s_l].setColour();245 buttons[10*s_r+s_l].Button.setLabel(""+huid); 246 Font font=new Font("楷体",Font.PLAIN,24); 247 buttons[10*s_r+s_l].Button.setFont(font);248 buttons[10*s_r+s_l].Button.setForeground(Color.white);249 } 250 }251 252 253 }254 255 256 257 public class kv{258 259 public int x;260 261 public int y;262 263 public kv(){264 this.x=100;265 this.y=100;266 267 }268 }269 270 } 271 public class ClearAction implements ActionListener {272 273 public ls[] buttons;274 public void actionPerformed(ActionEvent e) {275 276 for(int i=0;i<100;i++)277 { 278 System.out.print(" "+buttons[i].x);279 buttons[i].x=0;280 buttons[i].Button.setBackground(Color.white);281 buttons[i].Button.setText("");282 }283 } 284 public ClearAction(ls[] button) {285 buttons=button;286 }287 288 } 289 290 public class ls extends JFrame{291 292 JButton Button = new JButton(""); 293 int x; //湖泊陆地海洋标志294 int id; //地块或海洋号码295 public void setColour (){296 if(x==0)297 Button.setBackground(Color.gray);298 if(x==1)299 Button.setBackground(Color.green);300 if(x==2)301 Button.setBackground(Color.white);302 //Button.setText(""+id);303 }304 public ls(int i){305 this.x=i;306 Button.setBackground(Color.white);307 308 }309 }310 311 312 public static void main(String argv[]){313 314 new Haidao();315 }316 317 318 }
效果演示：
因时间问题，未细究其时间优化问题，代码有点粗糙，勿怪。
海岛问题之Java实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。