Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class GG {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int N = in.nextInt();
- int M = in.nextInt();
- int[][] arr = new int[N][M];
- int[][] bor = new int[N][M];
- boolean[][] vis = new boolean[N][M];
- int ans = 0;
- for(int i = 0; i < N; i++) {
- char[] tmp = in.next().toCharArray();
- for(int j = 0; j < M ;j++) {
- bor[i][j] = 0;
- arr[i][j] = (tmp[j] == '1') ? 1: 0;
- vis[i][j] = false;
- }
- }
- // DFS
- for(int i = 0; i < N; i++) {
- for(int j = 0; j < M; j++) {
- if(vis[i][j]) continue;
- if(arr[i][j] == 0) continue;
- Stack<Pair> s = new Stack();
- s.push(new Pair(i, j));
- while(!s.empty()) {
- Pair state = s.pop();
- int x = state.f;
- int y = state.s;
- if(vis[x][y]) continue;
- vis[x][y] = true;
- for(int ii = -1; ii <= 1; ii++) {
- for(int jj = -1; jj <= 1; jj++) {
- if(Math.abs(ii) == Math.abs(jj)) continue;
- // check if its a border
- boolean tmp = false;
- if(x + ii < 0 || x + ii >= N) {
- ans++;
- tmp = true;
- }
- if(y + jj < 0 || y + jj >= M) {
- ans++;
- tmp = true;
- }
- if(tmp) continue;
- // if not bordre
- int xx = x + ii;
- int yy = y + jj;
- if(arr[xx][yy] == 0) { // its a land
- if(ii < 0 && jj == 0) {
- bor[xx][yy] |= 1<<0;
- }else if(ii > 0 && jj == 0) {
- bor[xx][yy] |= 1<<3;
- }else if(ii == 0 && jj < 0) {
- bor[xx][yy] |= 1<<2;
- }else {
- bor[xx][yy] |= 1<<1;
- }
- if(bor[xx][yy] == ((1<<4) - 1)) ans -= 3;
- else ans++;
- }else{ // its a sea
- s.push(new Pair(xx, yy));
- }
- }
- }
- } // end DFS While
- }
- }
- System.out.println(ans);
- }
- }
- class Pair {
- int f, s;
- public Pair(int f, int s) {
- this.f = f;
- this.s = s;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement