結果
| 問題 | No.340 雪の足跡 |
| ユーザー |
 atn112323
|
| 提出日時 | 2016-02-06 10:58:33 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 13,814 bytes |
| コンパイル時間 | 2,895 ms |
| コンパイル使用メモリ | 87,304 KB |
| 実行使用メモリ | 140,864 KB |
| 最終ジャッジ日時 | 2024-09-21 20:46:37 |
| 合計ジャッジ時間 | 24,055 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 21 TLE * 11 |
ソースコード
import java.io.BufferedReader;import java.io.FileNotFoundException;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class Main {/*** This class represents a problem setting.*/class Problem implements IProblem {int[] WHN;int[][] B;@Overridepublic void set(ProblemReader reader) throws IOException {WHN = reader.nextIntArray();B = new int[WHN[2]][];for (int i = 0; i < WHN[2]; i++) {reader.nextInt();B[i] = reader.nextIntArray();}}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append(StringUtils.toString(WHN) + "\n");for (int i = 0; i < WHN[2]; i++) {sb.append(StringUtils.toString(B[i].length) + "\n");sb.append(StringUtils.toString(B[i]) + "\n");}sb.setLength(sb.length() - 1);return sb.toString();}}/*** Solver for the problem.* It's the most important part of codes in this file.*/class Solver implements IProblemSolver<Problem> {int[] DX = new int[]{1, 0, -1, 0};int[] DY = new int[]{0, 1, 0, -1};@Overridepublic String solve(Problem problem) {int W = problem.WHN[0], H = problem.WHN[1];int dist = solve(W, H, problem.B);if (dist >= 0) {return StringUtils.toString(dist);} else {return "Odekakedekinai..";}}private int solve(int W, int H, int[][] B) {int[][] connection = new int[W * H][2];for (int i = 0; i < B.length; i++) {for (int j = 1; j < B[i].length; j++) {int b0 = B[i][j - 1], b1 = B[i][j];if (b0 > b1) {int tmp = b0; b0 = b1; b1 = tmp;}int dx = (B[i][j] % W) - (B[i][j - 1] % W);int dy = (B[i][j] / W) - (B[i][j - 1] / W);for (int d = 0; d < 4; d++) {if (dx * DX[d] > 0 && dy * DY[d] == 0) {connection[b0][0] = Math.max(connection[b0][0], b1);break;} else if (dx * DX[d] == 0 && dy * DY[d] > 0) {connection[b0][1] = Math.max(connection[b0][1], b1);break;}}}}boolean[][] connected = new boolean[W * H][4];for (int y = 0; y < H; y++) {int x = 0;while (x < W) {while (x < W && connection[x + y * W][0] == 0) {x++;}if (x < W) {int b = x + y * W;int tb = connection[b][0];while (b != tb) {x++;int bb = x + y * W;connected[b][0] = true;connected[bb][2] = true;b = bb;tb = Math.max(tb, connection[b][0]);}}}}for (int x = 0; x < W; x++) {int y = 0;while (y < H) {while (y < H && connection[x + y * W][1] == 0) {y++;}if (y < H) {int b = x + y * W;int tb = connection[b][1];while (b != tb) {y++;int bb = x + y * W;connected[b][1] = true;connected[bb][3] = true;b = bb;tb = Math.max(tb, connection[b][1]);}}}}int[] visited = new int[W * H];for (int i = 0; i < W * H; i++) {visited[i] = -1;}Queue<Integer> que = new LinkedList<>();que.add(0);visited[0] = 0;while (que.size() > 0) {int b = que.poll();for (int d = 0; d < 4; d++) {if (connected[b][d]) {int xx = (b % W) + DX[d];int yy = (b / W) + DY[d];int bb = xx + yy * W;if (0 <= xx && xx < W && 0 <= yy && yy < H && visited[bb] < 0) {visited[bb] = visited[b] + 1;que.add(bb);}}}}return visited[W * H - 1];}}/*** This class is a solver to confirm the main solver.* This solver often works only for a problem with a small number setting.*/class Solver2 implements IProblemSolver<Problem> {@Overridepublic String solve(Problem problem) {// TODOreturn null;}}class Factory implements IProblemFactory<Problem> {@Overridepublic Problem newProblem() {// TODOreturn null;}@Overridepublic Problem newProblem(ProblemReader reader) throws IOException {Problem problem = new Problem();problem.set(reader);return problem;}}ProblemProcessor<Problem> processor;Main() {Init();}void Init() {ProblemProcessorConfig<Problem> config = new ProblemProcessorConfig<>();config.factory = new Factory();config.solver = new Solver();config.solver2 = new Solver2();processor = new ProblemProcessor<Problem>(config);}void process(String mode) throws IOException {processor.process(mode);}public static void main(String args[]) throws IOException {String mode = "solve";new Main().process(mode);}/*Common library*/interface IProblem {abstract void set(ProblemReader reader) throws IOException;}interface IProblemFactory<P extends IProblem> {abstract P newProblem();abstract P newProblem(ProblemReader reader) throws IOException;}interface IProblemSolver<P extends IProblem> {abstract String solve(P problem);}class ProblemReader {BufferedReader br = null;ProblemReader() {br = new BufferedReader(new InputStreamReader(System.in));}int nextInt() throws IOException {return StringUtils.toInt(br.readLine());}long nextLong() throws IOException {return StringUtils.toLong(br.readLine());}double nextDouble() throws IOException {return StringUtils.toDouble(br.readLine());}String nextString() throws IOException {return br.readLine();}int[] nextIntArray() throws IOException {return StringUtils.toIntArray(br.readLine());}long[] nextLongArray() throws IOException {return StringUtils.toLongArray(br.readLine());}double[] nextDoubleArray() throws IOException {return StringUtils.toDoubleArray(br.readLine());}String[] nextStringArray() throws IOException {return StringUtils.toStringArray(br.readLine());}int[] nextIntArray(int n) throws IOException {int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = nextInt();}return a;}long[] nextLongArray(int n) throws IOException {long[] a = new long[n];for (int i = 0; i < n; i++) {a[i] = nextLong();}return a;}double[] nextDoubleArray(int n) throws IOException {double[] a = new double[n];for (int i = 0; i < n; i++) {a[i] = nextDouble();}return a;}String[] nextStringArray(int n) throws IOException {String[] strs = new String[n];for (int i = 0; i < n; i++) {strs[i] = nextString();}return strs;}int[][] nextIntArray2(int n) throws IOException {int[][] a = new int[n][];for (int i = 0; i < n; i++) {a[i] = nextIntArray();}return a;}long[][] nextLongArray2(int n) throws IOException {long[][] a = new long[n][];for (int i = 0; i < n; i++) {a[i] = nextLongArray();}return a;}double[][] nextDoubleArray2(int n) throws IOException {double[][] a = new double[n][];for (int i = 0; i < n; i++) {a[i] = nextDoubleArray();}return a;}String[][] nextStringArray2(int n) throws IOException {String[][] strs = new String[n][];for (int i = 0; i < n; i++) {strs[i] = nextStringArray();}return strs;}void close() throws IOException {if (br != null) {br.close();}}}class ProblemCreator<P extends IProblem> {IProblemFactory<P> factory;ProblemCreator(IProblemFactory<P> factory) {this.factory = factory;}void create() throws FileNotFoundException {P problem = factory.newProblem();System.out.println(problem.toString());}}class ProblemSolverComparator<P extends IProblem> {IProblemFactory<P> factory;IProblemSolver<P> solver1, solver2;ProblemSolverComparator(IProblemFactory<P> factory, IProblemSolver<P> solver1, IProblemSolver<P> solver2) {this.factory = factory;this.solver1 = solver1;this.solver2 = solver2;}void compare() throws IOException {ProblemReader reader = null;try {reader = new ProblemReader();P problem = factory.newProblem(reader);String res1 = solver1.solve(problem);String res2 = solver2.solve(problem);if (res1.equals(res2)) {System.out.println(res1);} else {System.err.println(res1 + " " + res2);}} finally {if (reader != null) {reader.close();}}}}class ProblemAnswerer<P extends IProblem> {IProblemFactory<P> factory;IProblemSolver<P> solver;ProblemAnswerer(IProblemFactory<P> factory, IProblemSolver<P> solver) {this.factory = factory;this.solver = solver;}void answer() throws IOException {ProblemReader reader = null;try {reader = new ProblemReader();P problem = factory.newProblem(reader);String res = solver.solve(problem);System.out.println(res);} finally {if (reader != null) {reader.close();}}}}class ProblemProcessorConfig<P extends IProblem> {IProblemFactory<P> factory;IProblemSolver<P> solver, solver2;}class ProblemProcessor<P extends IProblem> {ProblemProcessorConfig<P> config;ProblemCreator<P> creator;ProblemSolverComparator<P> comparator;ProblemAnswerer<P> answerer;ProblemProcessor(ProblemProcessorConfig<P> config) {this.config = config;creator = new ProblemCreator<P>(config.factory);comparator = new ProblemSolverComparator<P>(config.factory, config.solver, config.solver2);answerer = new ProblemAnswerer<P>(config.factory, config.solver);}void process(String mode) throws IOException {switch (mode) {case "create":creator.create();break;case "debug":comparator.compare();break;case "solve":answerer.answer();break;}}}static class StringUtils {static String toString(int a) {return String.valueOf(a);}static String toString(long a) {return String.valueOf(a);}static String toString(double a) {return String.valueOf(a);}static String toString(String str) {return str;}static String toString(int[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + " ");} else {sb.append(a[i]);}}return sb.toString();}static String toString(long[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + " ");} else {sb.append(a[i]);}}return sb.toString();}static String toString(double[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + " ");} else {sb.append(a[i]);}}return sb.toString();}static String toString(String[] strs) {StringBuilder sb = new StringBuilder();for (int i = 0; i < strs.length; i++) {if (i < strs.length - 1) {sb.append(strs[i] + " ");} else {sb.append(strs[i]);}}return sb.toString();}static String toString(int[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static String toString(long[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static String toString(double[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static String toString(String[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static int toInt(String s) throws IOException {return Integer.parseInt(s);}static long toLong(String s) throws IOException {return Long.parseLong(s);}static double toDouble(String s) throws IOException {return Double.parseDouble(s);}static int[] toIntArray(String s) throws IOException {String[] tokens = s.split(" ");int[] a = new int[tokens.length];for (int i = 0; i < tokens.length; i++) {a[i] = Integer.parseInt(tokens[i]);}return a;}static long[] toLongArray(String s) throws IOException {String[] tokens = s.split(" ");long[] a = new long[tokens.length];for (int i = 0; i < tokens.length; i++) {a[i] = Long.parseLong(tokens[i]);}return a;}static double[] toDoubleArray(String s) throws IOException {String[] tokens = s.split(" ");double[] a = new double[tokens.length];for (int i = 0; i < tokens.length; i++) {a[i] = Double.parseDouble(tokens[i]);}return a;}static String[] toStringArray(String s) throws IOException {return s.split(" ");}}}