白駿2636号:チーズ




問題の説明


https://www.acmicpc.net/problem/2636
  • NxMメッシュの値は0または1です.
  • 1はチーズ、0は空気または穴を表します.
  • 空気に触れる面は溶けて消えます.
  • チーズに囲まれた0は穴です.
  • 方法

  • コアは、空気と孔を区別することができる必要がある.
  • (0,0)4部屋ナビゲーションで到達可能な0は、穴ではなく空気である.
  • pseudocode

    // -1은 공기, 0은 구멍, 1은 치즈입니다.
    while(처음에 치즈가 존재해야 시작할 수 있습니다){
    	BFS(0,0) // (0,0)에서 도달 가능한 0을 모두 -1로 만듭니다.
        
        for(모든(i,j)를 순회하면서){
        	// 여기서의 0은 구멍의 의미는 아닙니다. 녹은 치즈를 곧바로 -1로 만들면 다른 치즈의 검사에도 영향을 주기 때문에 0으로 만들었습니다. 알고리즘에 의해 다음 검사부터 -1이 됩니다. 
        	-1과 맞닿은 10으로 만듭니다. 
        }
        
        for(모든(i,j)를 순회하면서){    
        	-10으로 바꿉니다. // BFS는 (0,0)에서 0을 찾도록 설계되어 있습니다. -1은 인식하지 못하기 때문에 0으로 되돌립니다.
        }
        
        if(현재 남아있는 치즈의 개수가 0개면){
        	break
        }else{
        	남아있는 치즈의 개수를 갱신합니다.
        }
    }
    
    BFS(){
    	(0,0)에서 연결된 모든 0-1로 바꿉니다.
    }

    正解

    import java.util.*;
    
    class Main {
    	static int[] dx = { 1, 0, -1, 0 };
    	static int[] dy = { 0, -1, 0, 1 };
    	static int N, M, LastCheeze;
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		N = sc.nextInt();
    		M = sc.nextInt();
    		int[][] board = new int[N][M];
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < M; j++) {
    				int val = sc.nextInt();
    				board[i][j] = val;
    				LastCheeze += val;
    			}
    		}
    		
    		int time = 0;
    		while (LastCheeze!=0) { // 처음부터 치즈가 없다면 실행하지 말아야 합니다.
    			time++;
    			BFS(0, 0, board); // (0,0)과 연결된 0은 공기, 그렇지 않은 0은 구멍 // 공기를 모두 -1로 바꿉니다.
    			for (int i = 0; i < N; i++) {
    				for (int j = 0; j < M; j++) {
    					if (board[i][j] == 0 || board[i][j] == -1) continue; // 공기나 구멍은 패스합니다.
    					// 치즈의 4방 중 한 곳이라도 공기(-1)면 해당 치즈가 녹습니다.
    					for (int d = 0; d < 4; d++) {
    						int nx = i + dx[d];
    						int ny = j + dy[d];
    						if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == -1) {
    							board[i][j] = 0;
    							break;
    						}
    					}
    				}
    			}
    
    			int cnt = 0;
    			for (int i = 0; i < N; i++) {
    				for (int j = 0; j < M; j++) {
    					if (board[i][j] == -1) {
    						board[i][j] = 0; // 다음 BFS를 위해 -1로 바꾼 공기를 0으로 되돌립니다
    					} else if(board[i][j] == 1){ // 현재 남아있는 치즈의 개수를 샙니다.
    						cnt++;
    					}
    				}
    			}
    			if (cnt == 0) { // 남아있는 치즈가 없다면 while문을 종료합니다.
    				break;
    			} else {
    				LastCheeze = cnt;
    			}
    		}
    		System.out.println(time);
    		System.out.println(LastCheeze);
    	}
    
    	public static void BFS(int x, int y, int[][] board) {
    		board[x][y] = -1;
    		int[] temp = { x, y };
    		Queue<int[]> q = new LinkedList<int[]>();
    		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 < M && board[nx][ny] == 0) {
    					board[nx][ny] = -1;
    					int[] temp2 = { nx, ny };
    					q.add(temp2);
    				}
    			}
    		}
    	}
    }
    

    その他

  • BFSでは、錆びたチーズを判別できたが、このような設計はなかったため、完全な巡視(無効)が行われた.
  • 空気(-1)の横にチーズ(1)がある場合は、消去するチーズのリストに入れ、ナビゲーションが終了した後に一度に更新することができます.