[白俊14502]研究所(JAVA)


🔰 質問する


白駿14502号:研究所(Gold 5)

💡 方法


時間制限は2秒程度です
N,Mはいずれも3~8で,最大8個8×8=64個の格子である.64個の格子が0であっても、3つの壁を立てると64 C 3=約4万個になるので、すべての格子を立てるBrootForce方式に適しています.
壁を作った後にウイルスを伝播するのはBFSによって実行されますmakeWall(int cnt, int start)3つの
  • 壁(ゼロから3つの座標-シーケンス)
  • を立てる.spreadVirsus(int[][] map)
  • の3つの壁が立っていて、ウイルス伝播(BFS)
  • getSafeArea(int[][] map)
  • ウイルスが伝播した場合は、セキュリティ領域(2回繰り返し)
  • にアクセスします.

    💦 ミス

  • 0の場所では、壁の3つの座標を求めるときに、繰り返しシーケンスコードで記述されます.デバッグ中に気づき、コンビネーションコードに変更しました.
  • ウイルスが伝播した場合、1つのmap上ですべて実行され、最初の実行時にのみ正常なセキュリティ領域が求められ、最初の伝播したmap状態で実行され、正常な値はありません->さらにウイルスを伝播するための地図を作成し,それをパラメータとしてspreadVirus関数に渡す.
  • 🕑 所要時間


    25分
    以前は問題を解くのが難しくて、1時間以上かかりましたが、問題を解いてからすぐに問題を解いてしまいました.実力が上がった気がして、気持ちよかった!

    💻 に答える

    import java.io.*;
    import java.util.*;
    
    public class Main_14502 {
    	static int N, M;
    	static int map[][];
    	static boolean visited[][];
    	static List<int[]> list;
    	static int dx[] = { -1, 1, 0, 0 };
    	static int dy[] = { 0, 0, -1, 1 };
    	static int res; // 안전 영역 최대크기(정답)
    
    	public static void main(String[] args) throws Exception {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		M = Integer.parseInt(st.nextToken());
    
    		map = new int[N][M];
    		list = new ArrayList<int[]>(); // 0인 곳 좌표 저장
    		for (int i = 0; i < N; i++) {
    			st = new StringTokenizer(br.readLine());
    			for (int j = 0; j < M; j++) {
    				map[i][j] = Integer.parseInt(st.nextToken());
    				if (map[i][j] == 0)
    					list.add(new int[] { i, j });
    			}
    		}
    		// 벽 세우기 시작
    		makeWall(0, 0);
    		System.out.println(res);
    	}
    
    	private static void makeWall(int cnt, int start) {
    		if (cnt == 3) { // 벽 3개 다 세웠으면
    			visited = new boolean[N][M];
    			spreadVirus(map); // 바이러스 퍼뜨리기
    			return;
    		}
    		for (int i = start; i < list.size(); i++) {
    			int cur[] = list.get(i);
    			int cx = cur[0], cy = cur[1];
    			map[cx][cy] = 1; // 벽 세우기
    			makeWall(cnt + 1, i + 1);
    			map[cx][cy] = 0; // 벽 허물기
    		}
    
    	}
    
    	private static void spreadVirus(int[][] map) {
    		int newMap[][] = copy(map); // 바이러스 퍼뜨릴 map 새로 생성
    		Queue<int[]> q = new LinkedList<>();
    		// map 탐색하면서 바이러스 있는 곳(2) 전부 큐에 삽입
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < M; j++) {
    				if (newMap[i][j] == 2) {
    					q.add(new int[] { i, j });
    					visited[i][j] = true;
    				}
    			}
    		}
    		while (!q.isEmpty()) {
    			int cur[] = q.poll();
    			int cx = cur[0], cy = cur[1];
    			for (int i = 0; i < 4; i++) {
    				int nx = cx + dx[i];
    				int ny = cy + dy[i];
    				if (nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny] || newMap[nx][ny] == 1) // 범위 벗어났거나, 이미
    																										// 방문했거나, 벽이면 패스
    					continue;
    				if (newMap[nx][ny] == 0) {
    					newMap[nx][ny] = 2; // 바이러스 퍼뜨리기
    					q.offer(new int[] { nx, ny });
    					visited[nx][ny] = true;
    				}
    
    			}
    		}
    
    		// 바이러스 다 퍼뜨렸으면 안전영역 구하기
    		getSafeArea(newMap);
    
    	}
    
    	private static int[][] copy(int[][] map) {
    		int[][] tmp = new int[N][M];
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < M; j++) {
    				tmp[i][j] = map[i][j];
    			}
    		}
    		return tmp;
    	}
    
    	private static void getSafeArea(int[][] map) { // 안전 영역 구하기
    		int count = 0;
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < M; j++) {
    				if (map[i][j] == 0)
    					count++;
    			}
    		}
    		res = Math.max(res, count); // 정답 갱신
    	}
    
    }
    
    🌟 類似型の問題
    リファレンス