前提・実現したいこと
下記のアルゴリズムの問題に挑戦をしておりまして、Javaで実装してみたのですが
OutOfMemoryが解決できなくて正解を導き出すことができません。
どのように変更したら解決できそうかアドバイスをいただけたらと思います。
宜しくお願い致します。
【問題】
男女それぞれで15人の学級で、横6×縦5の座席で席替えを行います。
前後左右のいずれかに必ず異性が座る男女の配置が何通りあるかを
求めてください。(左右、前後などの反転は別々とカウントすることにします、また
個々の生徒がどこに座るかは無関係で、男女の配置のみを考えるものとします)
下記のようなパターンはNGなのでカウントできません。
NG例1 中央の男の前後左右すべてが男であるのでNG(女も同様)
列1 | 列2 | 列3 |
---|---|---|
女 | 男 | 女 |
男 | 男 | 男 |
女 | 男 | 女 |
NG例2 右端の上と左がどちらも女であるのでNG(男も同様)
列1 | 列2 | 列3 |
---|---|---|
男 | 男 | 女 |
女 | 女 | 女 |
発生している問題・エラーメッセージ
Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded at algolithm.Q69.clone(Q69.java:145) at algolithm.Q69.main(Q69.java:43)
該当ソースコード
package algolithm; import java.awt.Point; import java.time.LocalDateTime; import java.util.ArrayDeque; import java.util.Queue; public class Q69 { private static int side = 6; private static int length = 5; public static void main(String[] args) { System.out.println("処理開始:" + LocalDateTime.now()); int startSeatLineup[][] = setData(side + 2, length + 2); int count = 0; int sidezero = 0; int lengthzero = 0; Queue<int[][]> queue = new ArrayDeque<int[][]>(); queue.add(startSeatLineup); while (!queue.isEmpty()) { boolean zeroNone = true; int[][] seatLineupState = queue.remove(); //ゼロのある場所を特定する loopEnd: for (int k = 0; k < length + 2; k++) { for (int n = 0; n < side + 2; n++) { if (seatLineupState[k][n] == 0) { sidezero = k; lengthzero = n; zeroNone = false; break loopEnd; } } } if (zeroNone) { count++; print(seatLineupState); continue; } for (int d = 1; d <= 2; d++) { int[][] tmp = clone(seatLineupState); tmp[sidezero][lengthzero] = d; if (harfJudge(tmp)) { if (changeSheetCheck(tmp)) { queue.add(tmp); } } } } System.out.println(count + "通り"); System.out.println("処理終了:" + LocalDateTime.now()); } //男女それぞれの人数が全体の半数を超えているかいないかを判断する private static boolean harfJudge(int[][] tmp) { boolean halfAnswer = true; int manCount = 0; int womanCount = 0; for (int e = 0; e < length + 2; e++) { for (int w = 0; w < side + 2; w++) { if (tmp[e][w] == 1) { manCount++; } else if (tmp[e][w] == 2) { womanCount++; } } } if (manCount > side * length / 2 || womanCount > side * length / 2) { halfAnswer = false; } return halfAnswer; } //上下左右が全て同性でないかをチェックする private static boolean changeSheetCheck(int[][] seatLineup) { boolean check = false; loopEnd: for (int r = 0; r < length + 2; r++) { for (int q = 0; q < side + 2; q++) { if (seatLineup[r][q] == -1) { continue; } else if (seatLineup[r][q] == 0) { break loopEnd; } check = false; Point point = new Point(r, q); point.translate(0, -1); if (!(seatLineup[point.x][point.y] == seatLineup[r][q]) && !(seatLineup[point.x][point.y] == -1)) { check = true; } point.setLocation(r, q); point.translate(0, 1); if (!(seatLineup[point.x][point.y] == seatLineup[r][q]) && !(seatLineup[point.x][point.y] == -1)) { check = true; } point.setLocation(r, q); point.translate(-1, 0); if (!(seatLineup[point.x][point.y] == seatLineup[r][q]) && !(seatLineup[point.x][point.y] == -1)) { check = true; } point.setLocation(r, q); point.translate(1, 0); if (!(seatLineup[point.x][point.y] == seatLineup[r][q]) && !(seatLineup[point.x][point.y] == -1)) { check = true; } if (!check) { break loopEnd; } } } return check; } //初期状態のセット 誰も席に座っていない private static int[][] setData(int side, int length) { int seatLineup[][] = new int[length][side]; for (int i = 0; i < length; i++) { for (int j = 0; j < side; j++) { if (i == 0 || i == length - 1 || j == 0 || j == side - 1) { seatLineup[i][j] = -1; } else { seatLineup[i][j] = 0; } System.out.print(seatLineup[i][j] + " "); } System.out.println(""); } System.out.println(""); return seatLineup; } private static int[][] clone(int[][] target) { int[][] res = new int[length + 2][side + 2]; for (int col = 0; col < length + 2; col++) { res[col] = target[col].clone(); } return res; } private static void print(int[][] seatLineupState) { for (int s = 0; s < length + 2; s++) { for (int v = 0; v < side + 2; v++) { if (seatLineupState[s][v] == -1) { continue; } if (seatLineupState[s][v] == 1) { System.out.print("●" + " "); } else { System.out.print("○" + " "); } } System.out.println(""); } } }
試したこと
下記でクローンしているところを、クローンを使わずに別の配列にひとつずつ値を詰め直してみたりもしましたが結果は変わりませんでした。
private static int[][] clone(int[][] target) { int[][] res = new int[length + 2][side + 2]; for (int col = 0; col < length + 2; col++) { res[col] = target[col].clone(); } return res; }
回答3件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/03/23 09:32