[白俊20058]魔法使いサメと吹雪(JAVA)

🔰 質問する

白駿20058号:魔法使いサメと火の嵐

💡 方法

シミュレーション、アレイ回転、dfs(bfs)問題

部分配列で時計回りに90度

回転する.

回転終了後,隣接する氷が3個未満の格子は氷サイズ−1(4室探索)

であった.

最終配列の総氷と最大塊度(図ナビゲーション)

これは配列回転が困難な問題である.
最初は、次のように回転しようとしました.

for (int l = 0; l < k / 2; l++) {
			for (int i = l; i < k - l; i++) {
				temp[x + l][y + i] = map[x + k - 1 - i][y + l]; // 위쪽 줄
				temp[x + i][y + k - 1 - l] = map[x + l][y + i]; // 오른쪽
				temp[x + k - 1 - l][y + i] = map[x + k - 1 - i][y + k - 1 - l]; // 아래
				temp[x + i][y + l] = map[x + k - 1 - l][y + i]; // 왼
			}
		}

コードを見ればわかりますが、インデックスのせいで頭が痛くて死にそうになりました・・・🤔

💦 ミス

アレイ90度回転エラー
誤って4 X 4アレイの2 X 2部分アレイを時計回りに回転
配列回転方式を正確に理解しても、上述した方式を実現するには長い時間がかかる.

🌟 時計回りに90度回転する簡単な方法

k=2^L(ローカル配列サイズ)

	private static void rotate(int x, int y, int k, int[][] copy) {

		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				map[x + j][y + k - 1 - i] = copy[x + i][y + j];
			}
		}
	}

アレイのコピー先のエラー宣言->タイムアウト
回転を行うには、既存の配列をコピーする必要があります.
ただし、2^Nアレイの一部のアレイを回転させるたびに、アレイコピー位置が宣言され、タイムアウトが発生します.
それが分からず、DFSをBFSに変えて、かなり怪我をしたような・・・ははは

氷がなくなったときは逐次漸進的に除去を模索することはできない.そうなると、氷が1枚消えて、後ろの氷も一緒に消えてしまうからです.そのため、減少した氷の座標を一度に保存し、最後に氷を減らす作業を行う必要がある.

🕑 所要時間

2時間50分

💻 に答える

import java.io.*;
import java.util.*;

public class Main {
	static int N, Q, M;
	static int map[][];
	static int L[];
	static boolean visited[][];
	static int iceCnt; // 덩어리가 차지하는 칸 개수

	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());
		Q = Integer.parseInt(st.nextToken()); // 파이어스톰 시전 회수
		M = (int) Math.pow(2, N); // M=2^N

		map = new int[M][M];
		visited = new boolean[M][M];
		L = new int[Q];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < Q; i++)
			L[i] = Integer.parseInt(st.nextToken());

		for (int i = 0; i < Q; i++) { // Q번의 파이어스톰 실행
			FireStorm(L[i]);
		}

		// 1.남아있는 얼음 양
		int sum = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				sum += map[i][j];
			}
		}
		// 2. 가장 큰 덩어리가 차지하는 개수
		int res = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				if (!visited[i][j] && map[i][j] != 0) {
					iceCnt = 1;
					dfs(i, j);
					res = Math.max(res, iceCnt);
				}
			}
		}
		System.out.println(sum);
		System.out.println(res);
	}

	private static void dfs(int x, int y) { // 얼음 덩어리 개수
		visited[x][y] = true;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= M || ny < 0 || ny >= M)
				continue;
			if (!visited[nx][ny] && map[nx][ny] > 0) {
				dfs(nx, ny);
				iceCnt++;

			}
		}
	}

	private static void FireStorm(int l) { // 파이어 스톰

		int K = (int) Math.pow(2, l); // K = 2^l

		int[][] copy = copy(map);
		for (int i = 0; i < M; i = i + K) { // KxK 크기의 격자 90도 회전
			for (int j = 0; j < M; j = j + K) {
				rotate(i, j, K, copy);
			}
		}
		decreaseIce(); // 회전 끝나면 얼음 줄이기 시작
	}

	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	private static void decreaseIce() { // 얼음 줄이기
		List<int[]> list = new ArrayList<>();

		for (int x = 0; x < M; x++) {
			for (int y = 0; y < M; y++) {
				int cnt = 0; // 얼음이 있는 칸 수
				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 0 || nx >= M || ny < 0 || ny >= M)
						continue;
					if (map[nx][ny] > 0)
						cnt++;
				}
				if (cnt < 3) // 얼음있는 칸이 3칸 미만이면
					list.add(new int[] { x, y });
			}

		}
		for (int i = 0; i < list.size(); i++) {
			int[] cur = list.get(i);
			if (map[cur[0]][cur[1]] > 0) {
				map[cur[0]][cur[1]] -= 1;
			}
		}
	}

	private static void rotate(int x, int y, int k, int[][] copy) { // 시계방향 90도 회전

		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				map[x + j][y + k - 1 - i] = copy[x + i][y + j];
			}
		}
	}

	private static int[][] copy(int[][] map) {
		int data[][] = new int[M][M];
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++)
				data[i][j] = map[i][j];
		}
		return data;
	}
}

🌟 類似型の問題
[白準20327]回転配列6(Gold 3)
❗解けた良い質問
[白駿17276]回転アレイ(Silver 2)
[白俊16926]回転配列1(Silver 1)
[白俊16927]回転配列2(Gold 5)
[白俊16935]回転配列3(Silver 1)
[白俊17406]回転配列4(Gold 4)
リファレンス
[白俊]20058号-魔法使いサメと吹雪(java)
2 Dアレイ回転Rotate(Java)