首页 > 代码库 > 海岛问题之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 }
View Code

 

有其引发出一小游戏: 即类似扫雷,在水域上随意添加陆地,然后计算海洋个数,湖泊个数和陆地边界线长度。

  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 }
View Code

 

 

效果演示:

因时间问题,未细究其时间优化问题,代码有点粗糙,勿怪。

海岛问题之Java实现