#74624 (Java21) No.340 雪の足跡

提出ソース

結果

問題	No.340 雪の足跡
ユーザー	atn112323
提出日時	2016-02-06 10:58:33
言語	Java21 (openjdk 21)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	13,814 bytes
コンパイル時間	3,631 ms
コンパイル使用メモリ	90,592 KB
実行使用メモリ	155,112 KB
最終ジャッジ日時	2023-10-21 19:25:20
合計ジャッジ時間	24,406 ms
ジャッジサーバーID （参考情報）	judge9 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	59 ms 53,656 KB
testcase_01	AC	59 ms 53,672 KB
testcase_02	AC	58 ms 51,696 KB
testcase_03	AC	59 ms 53,668 KB
testcase_04	AC	58 ms 53,672 KB
testcase_05	AC	58 ms 53,656 KB
testcase_06	AC	58 ms 53,660 KB
testcase_07	AC	59 ms 53,660 KB
testcase_08	AC	59 ms 53,660 KB
testcase_09	AC	59 ms 53,660 KB
testcase_10	AC	58 ms 53,672 KB
testcase_11	AC	96 ms 55,448 KB
testcase_12	AC	81 ms 54,516 KB
testcase_13	AC	91 ms 55,216 KB
testcase_14	AC	288 ms 64,668 KB
testcase_15	AC	300 ms 65,224 KB
testcase_16	AC	230 ms 60,224 KB
testcase_17	AC	323 ms 64,704 KB
testcase_18	AC	281 ms 63,888 KB
testcase_19	AC	333 ms 64,776 KB
testcase_20	TLE	-
testcase_21	AC	578 ms 65,776 KB
testcase_22	AC	338 ms 117,760 KB
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	AC	277 ms 60,680 KB
testcase_27	AC	156 ms 58,760 KB
testcase_28	AC	308 ms 60,828 KB
testcase_29	TLE	-
testcase_30	AC	856 ms 105,440 KB
testcase_31	TLE	-
testcase_32	TLE	-
testcase_33	TLE	-
testcase_34	TLE	-
testcase_35	TLE	-
testcase_36	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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;
		
		@Override
		public 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();
			}
		}
		
		@Override
		public 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};
		
		@Override
		public 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> {

		@Override
		public String solve(Problem problem) {
			// TODO
			return null;
		}
	}
	
	class Factory implements IProblemFactory<Problem> {

		@Override
		public Problem newProblem() {
			// TODO
			return null;
		}

		@Override
		public 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(" ");
		}
	}
}

yukicoder

結果

テストケース

ソースコード