Submission #1131230
Source Code Expand
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.HashSet; import java.util.InputMismatchException; import java.util.LinkedList; import java.util.Queue; public class Main { InputStream is; int __t__ = 1; int __f__ = 0; int __FILE_DEBUG_FLAG__ = __f__; String __DEBUG_FILE_NAME__ = "src/T"; FastScanner in; PrintWriter out; HashSet<String> hash = new HashSet<>(); class Pair { int turn; String[] s; Pair(int turn, String[] s) { this.turn = turn; this.s = s; } Pair covert(Pair p, int ii, int jj) { int n = s.length; char[][] tmp = new char[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { tmp[i][j] = s[i].charAt(j); } } char[] c = new char[n]; for (int j = 0; j < n; j++) { c[j] = tmp[ii][j]; } for (int i = 0; i < n; i++) { tmp[i][jj] = c[i]; } String[] next = new String[n]; for (int i = 0; i < n; i++) { next[i] = String.valueOf(tmp[i]); } return new Pair(turn + 1, next); } boolean isOk() { int n = s.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (s[i].charAt(j) == '.') return false; } } return true; } } String toKey(String[] s) { String res = ""; for (int i = 0; i < s.length; i++) { res += s[i] + " "; } return res; } public void solve() { int n = in.nextInt(); String[] a = in.nextStringArray(n); if (n > 3) { return; } Queue<Pair> q = new LinkedList<>(); q.add(new Pair(0, a)); while (!q.isEmpty()) { Pair cur = q.poll(); if (cur.isOk()) { System.out.println(cur.turn); return; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Pair next = cur.covert(cur, i, j); String key = toKey(next.s); if (!hash.contains(key)) { hash.add(key); q.add(next); } } } } System.out.println("-1"); } public void run() { if (__FILE_DEBUG_FLAG__ == __t__) { try { is = new FileInputStream(__DEBUG_FILE_NAME__); } catch (FileNotFoundException e) { // TODO 自動生成された catch ブロック e.printStackTrace(); } System.out.println("FILE_INPUT!"); } else { is = System.in; } in = new FastScanner(is); out = new PrintWriter(System.out); solve(); } public static void main(String[] args) { new Main().run(); } public void mapDebug(int[][] a) { System.out.println("--------map display---------"); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { System.out.printf("%3d ", a[i][j]); } System.out.println(); } System.out.println("----------------------------"); System.out.println(); } public void debug(Object... obj) { System.out.println(Arrays.deepToString(obj)); } class FastScanner { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; public FastScanner(InputStream stream) { this.stream = stream; //stream = new FileInputStream(new File("dec.in")); } int read() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } boolean isEndline(int c) { return c == '\n' || c == '\r' || c == -1; } int nextInt() { return Integer.parseInt(next()); } int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) array[i] = nextInt(); return array; } int[][] nextIntMap(int n, int m) { int[][] map = new int[n][m]; for (int i = 0; i < n; i++) { map[i] = in.nextIntArray(m); } return map; } long nextLong() { return Long.parseLong(next()); } long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) array[i] = nextLong(); return array; } long[][] nextLongMap(int n, int m) { long[][] map = new long[n][m]; for (int i = 0; i < n; i++) { map[i] = in.nextLongArray(m); } return map; } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) array[i] = nextDouble(); return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][m]; for (int i = 0; i < n; i++) { map[i] = in.nextDoubleArray(m); } return map; } String next() { int c = read(); while (isSpaceChar(c)) c = read(); StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = read(); } while (!isSpaceChar(c)); return res.toString(); } String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) array[i] = next(); return array; } String nextLine() { int c = read(); while (isEndline(c)) c = read(); StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = read(); } while (!isEndline(c)); return res.toString(); } } }
Submission Info
Submission Time | |
---|---|
Task | B - Row to Column |
User | hiro116s |
Language | Java8 (OpenJDK 1.8.0) |
Score | 300 |
Code Size | 5719 Byte |
Status | WA |
Exec Time | 104 ms |
Memory | 24276 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | 0 / 1000 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt |
Subtask | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 73 ms | 19028 KB |
0_01.txt | AC | 67 ms | 21332 KB |
0_02.txt | AC | 69 ms | 19284 KB |
0_03.txt | AC | 71 ms | 19412 KB |
0_04.txt | AC | 96 ms | 22612 KB |
1_00.txt | AC | 69 ms | 20052 KB |
1_01.txt | AC | 69 ms | 21332 KB |
1_02.txt | AC | 96 ms | 21716 KB |
1_03.txt | AC | 97 ms | 20692 KB |
1_04.txt | AC | 95 ms | 24020 KB |
1_05.txt | AC | 97 ms | 24148 KB |
1_06.txt | AC | 94 ms | 22100 KB |
1_07.txt | AC | 99 ms | 24148 KB |
1_08.txt | AC | 77 ms | 20436 KB |
1_09.txt | AC | 92 ms | 21844 KB |
1_10.txt | AC | 94 ms | 21844 KB |
1_11.txt | AC | 75 ms | 19284 KB |
1_12.txt | AC | 73 ms | 21204 KB |
1_13.txt | AC | 75 ms | 19796 KB |
1_14.txt | AC | 96 ms | 23760 KB |
2_00.txt | WA | 96 ms | 24148 KB |
2_01.txt | WA | 95 ms | 22228 KB |
2_02.txt | WA | 98 ms | 24020 KB |
2_03.txt | WA | 99 ms | 24276 KB |
2_04.txt | WA | 87 ms | 20564 KB |
2_05.txt | WA | 97 ms | 22100 KB |
2_06.txt | WA | 98 ms | 22996 KB |
2_07.txt | WA | 85 ms | 23636 KB |
2_08.txt | WA | 97 ms | 22228 KB |
2_09.txt | WA | 94 ms | 22356 KB |
2_10.txt | WA | 97 ms | 22228 KB |
2_11.txt | WA | 89 ms | 23508 KB |
2_12.txt | WA | 98 ms | 24020 KB |
2_13.txt | WA | 97 ms | 23892 KB |
2_14.txt | WA | 96 ms | 24148 KB |
2_15.txt | WA | 95 ms | 23508 KB |
2_16.txt | WA | 95 ms | 22228 KB |
2_17.txt | WA | 95 ms | 22100 KB |
2_18.txt | WA | 96 ms | 22996 KB |
2_19.txt | WA | 104 ms | 22868 KB |
2_20.txt | WA | 94 ms | 18644 KB |
2_21.txt | WA | 94 ms | 21844 KB |
2_22.txt | WA | 98 ms | 22228 KB |