Advertisement
Guest User

Untitled

a guest
Mar 25th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.00 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class GG {
  5.  
  6.     public static void main(String[] args) {
  7.         Scanner in = new Scanner(System.in);
  8.         int N = in.nextInt();
  9.         int M = in.nextInt();
  10.  
  11.         int[][] arr = new int[N][M];
  12.         int[][] bor = new int[N][M];
  13.         boolean[][] vis = new boolean[N][M];
  14.  
  15.         int ans = 0;
  16.         for(int i = 0; i < N; i++)  {
  17.             char[] tmp = in.next().toCharArray();
  18.             for(int j = 0; j < M ;j++) {
  19.                 bor[i][j] = 0;
  20.                 arr[i][j] = (tmp[j] == '1') ? 1: 0;
  21.                 vis[i][j] = false;
  22.             }
  23.         }
  24.  
  25.         // DFS
  26.         for(int i = 0; i < N; i++) {
  27.             for(int j = 0; j < M; j++) {
  28.                 if(vis[i][j]) continue;
  29.                 if(arr[i][j] == 0) continue;
  30.  
  31.                 Stack<Pair> s = new Stack();
  32.                 s.push(new Pair(i, j));
  33.  
  34.                 while(!s.empty()) {
  35.                     Pair state = s.pop();
  36.                     int x = state.f;
  37.                     int y = state.s;
  38.  
  39.                     if(vis[x][y]) continue;
  40.                     vis[x][y] = true;
  41.  
  42.                     for(int ii = -1; ii <= 1; ii++) {
  43.                         for(int jj = -1; jj <= 1; jj++)  {
  44.                             if(Math.abs(ii) == Math.abs(jj)) continue;
  45.  
  46.                             // check if its a border   
  47.                             boolean tmp = false;
  48.                             if(x + ii < 0 || x + ii >= N) {
  49.                                 ans++;
  50.                                 tmp = true;
  51.                             }
  52.                             if(y + jj < 0 || y + jj >= M) {
  53.                                 ans++;
  54.                                 tmp = true;
  55.                             }
  56.                             if(tmp) continue;
  57.  
  58.                             // if not bordre
  59.                            
  60.                             int xx = x + ii;
  61.                             int yy = y + jj;
  62.                             if(arr[xx][yy] == 0) { // its a land
  63.                                 if(ii <  0 && jj == 0) {
  64.                                     bor[xx][yy] |= 1<<0;
  65.                                 }else if(ii > 0 && jj == 0) {
  66.                                     bor[xx][yy] |= 1<<3;
  67.                                 }else if(ii == 0 && jj < 0) {
  68.                                     bor[xx][yy] |= 1<<2;
  69.                                 }else {
  70.                                     bor[xx][yy] |= 1<<1;
  71.                                 }
  72.  
  73.                                
  74.                                 if(bor[xx][yy] == ((1<<4) - 1)) ans -= 3;
  75.                                 else ans++;
  76.  
  77.                                
  78.                             }else{  // its a sea
  79.                                 s.push(new Pair(xx, yy));
  80.                             }
  81.  
  82.                         }
  83.                     }
  84.  
  85.                 } // end DFS While
  86.  
  87.             }
  88.         }
  89.  
  90.         System.out.println(ans);
  91.  
  92.     }
  93. }
  94.  
  95. class Pair {
  96.     int f, s;
  97.  
  98.     public Pair(int f, int s) {
  99.         this.f = f;
  100.         this.s = s;
  101.     }
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement