結果
問題 | No.359 門松行列 |
ユーザー |
|
提出日時 | 2016-05-31 01:29:34 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 228 ms / 2,000 ms |
コード長 | 4,372 bytes |
コンパイル時間 | 2,486 ms |
コンパイル使用メモリ | 80,680 KB |
実行使用メモリ | 43,336 KB |
最終ジャッジ日時 | 2024-10-07 20:07:16 |
合計ジャッジ時間 | 6,701 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
package yukicoder;import java.util.ArrayList;import java.util.Comparator;import java.util.Scanner;public class Main{public static void main(String[] args) {new Main().solve();// new Q359().naive();}void naive() {Scanner sc = new Scanner(System.in);int T = sc.nextInt();for (int i = 0; i < T; i++) {int[][] table = new int[3][3];int L = sc.nextInt();int x1 = -1;int y1 = -1;int x2 = -1;int y2 = -1;for (int j = 0; j < 3; j++) {for (int k = 0; k < 3; k++) {table[j][k] = sc.nextInt();if (table[j][k] == 0) {if (x1 == -1 && y1 == -1) {x1 = k;y1 = j;} else {x2 = k;y2 = j;}}}}int sum = 0;ArrayList<Integer> ans=new ArrayList<>();for (int j = 1; j < L; j++) {int[][] d = table;d[y1][x1] = j;d[y2][x2] = L - j;if (ok(d)) {sum++;ans.add(d[y1][x1]);}}ans.sort(new Comparator<Integer>(){@Overridepublic int compare(Integer o1, Integer o2) {return Integer.compare(o1, o2);}});// for(int j=0;j<ans.size();j++){// System.out.println(ans.get(j));// }System.out.println(sum);}}void solve() {Scanner sc = new Scanner(System.in);int T = sc.nextInt();for (int i = 0; i < T; i++) {ArrayList<Singularity> singu = new ArrayList<>();ArrayList<Integer> checked = new ArrayList<>();int L = sc.nextInt();int[][] table = new int[3][3];int x1 = -1;int y1 = -1;int x2 = -1;int y2 = -1;ArrayList<Integer> cand = new ArrayList<>();for (int j = 0; j < 3; j++) {for (int k = 0; k < 3; k++) {table[j][k] = sc.nextInt();if (table[j][k] == 0) {if (x1 == -1 && y1 == -1) {x1 = k;y1 = j;} else {x2 = k;y2 = j;}} else {cand.add(table[j][k]);}}}cand.add(L/2);cand.add(0);cand.add(L);for (int j = 0; j < cand.size(); j++) {singu = add_singu(cand.get(j), table, x1, y1, x2, y2, L, singu, checked);}singu.sort(new Comparator<Singularity>() {@Overridepublic int compare(Singularity o1, Singularity o2) {return Integer.compare(o1.num, o2.num);}});// for(int j=0;j<singu.size();j++){// System.out.println(singu.get(j).num+" "+singu.get(j).isKado);// }int sum = 0;for (int j = 0; j < singu.size(); j++) {if (singu.get(j).isKado) {if (j + 1 < singu.size() && singu.get(j + 1).isKado) {int pre = j;while (j + 1 < singu.size() && singu.get(j + 1).isKado)j++;sum += singu.get(j).num - singu.get(pre).num + 1;} else {sum++;}j++;}}System.out.println(sum);}}boolean isKaramatsu(int a, int b, int c) {if (a <= 0 || b <= 0 || c <= 0)return false;if (a == b || b == c || c == a)return false;if (a < b && b > c)return true;if (a > b && b < c)return true;return false;}boolean ok(int[][] table) {for (int i = 0; i < 3; i++) {if (!isKaramatsu(table[i][0], table[i][1], table[i][2])) {return false;}if (!isKaramatsu(table[0][i], table[1][i], table[2][i])) {return false;}}if (!isKaramatsu(table[0][0], table[1][1], table[2][2])) {return false;}if (!isKaramatsu(table[0][2], table[1][1], table[2][0])) {return false;}return true;}class Singularity {int num;boolean isKado;Singularity(int num, boolean isKado) {this.num = num;this.isKado = isKado;}}ArrayList add_singu(int x, int[][] table, int x1, int y1, int x2, int y2, int L, ArrayList singu, ArrayList used) {int[][] d = table;for (int l = 0; l < 3; l++) {int dd = 1;d[y1][x1] = x + (l == 0 ? dd : l == 1 ? -dd : 0);d[y2][x2] = L - d[y1][x1];if (!used.contains(d[y1][x1])) {singu.add(new Singularity(d[y1][x1], ok(d)));used.add(d[y1][x1]);}}for (int l = 0; l < 3; l++) {int dd = 1;d[y2][x2] = x + (l == 0 ? dd : l == 1 ? -dd : 0);d[y1][x1] = L - d[y2][x2];if (!used.contains(d[y1][x1])) {singu.add(new Singularity(d[y1][x1], ok(d)));used.add(d[y1][x1]);}}return singu;}// void showMt(int[][] table){// for(int i=0;i<3;i++){// for(int j=0;j<3;j++){// System.out.print(table[i][j]+(j!=2?" ":"\n"));// }// }// }}