白駿2468号:安全区域




問題の説明

  • https://www.acmicpc.net/problem/2468
  • の雨量がhであれば、h>=board[i][j](i,j)地域は水没する.
  • 浸水地域を除いて、残りの地域が移動可能な場所に接続されている島の数を求めた.
  • 雨が1~100降ったとき、島の個数が最も多かったのはどのくらいの島だったか.
  • 方法

  • 水没領域を求めるBFSと水没後の島の数を求めるBFSをそれぞれ実行した.
  • pseudocode

    for(h는 1부터 가장 높은 지점의 숫자까지){
    	// 높이가 h 이하인 지역이 물에 잠깁니다.
        for(i는 0부터 N까지){
            for(j는 0부터 N까지){
                BFS(i,j,h);
            }
        }
        // 섬의 개수를 구합니다.
        for(i는 0부터 N까지){
            for(j는 0부터 N까지){
    	        // 1001은 임의의 숫자입니다. 저는 물에 잠긴 지역을 1002로 표현했습니다.
                // 섬을 구하기 위해서는 100(지역의 최대높이) < x <1002(물에 잠긴 걸 표현)를 만족하는 x로 BFS를 실행해야 합니다.
                BFS(i,j,1001); 
            }
        }
        
    }
    

    正解

    import java.io.*;
    import java.util.*;
    
    class Main {
    	static int MaxHeight = 0;
    	static int[] dx = { 1, 0, -1, 0 };
    	static int[] dy = { 0, -1, 0, 1 };
    	static int N;
    	static int Answer = 1;
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		N = sc.nextInt();
    		int[][] board = new int[N][N];
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				int val = sc.nextInt();
    				board[i][j] = val;
    				MaxHeight = Math.max(val, MaxHeight);
    			}
    		}
    		for (int h = 1; h <= MaxHeight; h++) {
    			int[][] CopyBoard = new int[N][N];
    			for (int i = 0; i < N; i++) {
    				CopyBoard[i] = board[i].clone();
    			}
    
    			for (int i = 0; i < N; i++) {
    				for (int j = 0; j < N; j++) {
    					BFS(i, j, h, CopyBoard);
    				}
    			}
    
    			int cnt = 0;
    			for (int i = 0; i < N; i++) {
    				for (int j = 0; j < N; j++) {
    					if (CopyBoard[i][j] < 1002) {
    						cnt++;
    						BFS(i, j, 1001, CopyBoard);
    					}
    				}
    			}
    			Answer = Math.max(Answer, cnt);
    		}
    		System.out.println(Answer);
    
    	}
    
    	public static void BFS(int x, int y, int h, int[][] board) {
    		Queue<int[]> q = new LinkedList<int[]>();
    		int[] temp = { x, y };
    		q.add(temp);
    		while (!q.isEmpty()) {
    			int[] now = q.poll();
    			for (int d = 0; d < 4; d++) {
    				int nx = now[0] + dx[d];
    				int ny = now[1] + dy[d];
    				if (0 <= nx && nx < N && 0 <= ny && ny < N && board[nx][ny] <= h) {
    					int[] next = { nx, ny };
    					q.add(next);
    					board[nx][ny] = 1002;
    				}
    			}
    		}
    	}
    }