#859980 (Java21) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	tsukammo
提出日時	2023-04-15 13:46:16
言語	Java21 (openjdk 21)
結果	AC
実行時間	139 ms / 3,000 ms
コード長	10,675 bytes
コンパイル時間	3,393 ms
コンパイル使用メモリ	94,052 KB
実行使用メモリ	55,984 KB
スコア	11,870
最終ジャッジ日時	2023-04-15 13:46:40
合計ジャッジ時間	19,023 ms
ジャッジサーバーID （参考情報）	judge12 / judge16
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	107 ms 53,972 KB
testcase_01	AC	111 ms 53,656 KB
testcase_02	AC	109 ms 54,020 KB
testcase_03	AC	109 ms 54,016 KB
testcase_04	AC	125 ms 53,716 KB
testcase_05	AC	107 ms 53,880 KB
testcase_06	AC	107 ms 53,640 KB
testcase_07	AC	106 ms 52,024 KB
testcase_08	AC	105 ms 53,748 KB
testcase_09	AC	109 ms 54,268 KB
testcase_10	AC	108 ms 53,880 KB
testcase_11	AC	106 ms 55,984 KB
testcase_12	AC	132 ms 53,976 KB
testcase_13	AC	106 ms 54,188 KB
testcase_14	AC	116 ms 53,672 KB
testcase_15	AC	107 ms 53,664 KB
testcase_16	AC	108 ms 53,936 KB
testcase_17	AC	107 ms 53,932 KB
testcase_18	AC	107 ms 53,668 KB
testcase_19	AC	112 ms 53,852 KB
testcase_20	AC	132 ms 53,912 KB
testcase_21	AC	106 ms 53,992 KB
testcase_22	AC	108 ms 53,968 KB
testcase_23	AC	109 ms 54,028 KB
testcase_24	AC	108 ms 53,780 KB
testcase_25	AC	121 ms 53,812 KB
testcase_26	AC	107 ms 54,284 KB
testcase_27	AC	107 ms 54,104 KB
testcase_28	AC	132 ms 53,100 KB
testcase_29	AC	108 ms 53,932 KB
testcase_30	AC	107 ms 53,920 KB
testcase_31	AC	111 ms 53,876 KB
testcase_32	AC	107 ms 53,932 KB
testcase_33	AC	106 ms 53,732 KB
testcase_34	AC	110 ms 53,684 KB
testcase_35	AC	106 ms 54,020 KB
testcase_36	AC	104 ms 54,044 KB
testcase_37	AC	107 ms 53,920 KB
testcase_38	AC	108 ms 53,948 KB
testcase_39	AC	105 ms 53,804 KB
testcase_40	AC	105 ms 54,072 KB
testcase_41	AC	112 ms 53,740 KB
testcase_42	AC	106 ms 53,976 KB
testcase_43	AC	109 ms 54,356 KB
testcase_44	AC	109 ms 53,764 KB
testcase_45	AC	139 ms 53,924 KB
testcase_46	AC	112 ms 53,972 KB
testcase_47	AC	112 ms 54,016 KB
testcase_48	AC	111 ms 53,664 KB
testcase_49	AC	107 ms 54,416 KB
testcase_50	AC	107 ms 53,764 KB
testcase_51	AC	105 ms 53,972 KB
testcase_52	AC	111 ms 53,960 KB
testcase_53	AC	134 ms 53,764 KB
testcase_54	AC	108 ms 53,688 KB
testcase_55	AC	109 ms 54,224 KB
testcase_56	AC	113 ms 53,700 KB
testcase_57	AC	109 ms 54,440 KB
testcase_58	AC	107 ms 53,656 KB
testcase_59	AC	107 ms 53,932 KB
testcase_60	AC	106 ms 54,100 KB
testcase_61	AC	134 ms 54,224 KB
testcase_62	AC	109 ms 53,704 KB
testcase_63	AC	111 ms 53,772 KB
testcase_64	AC	109 ms 53,948 KB
testcase_65	AC	112 ms 53,952 KB
testcase_66	AC	112 ms 53,604 KB
testcase_67	AC	105 ms 53,860 KB
testcase_68	AC	108 ms 53,872 KB
testcase_69	AC	107 ms 53,676 KB
testcase_70	AC	110 ms 53,824 KB
testcase_71	AC	110 ms 54,108 KB
testcase_72	AC	107 ms 53,996 KB
testcase_73	AC	109 ms 53,724 KB
testcase_74	AC	111 ms 53,836 KB
testcase_75	AC	107 ms 53,952 KB
testcase_76	AC	108 ms 53,980 KB
testcase_77	AC	107 ms 52,796 KB
testcase_78	AC	133 ms 53,996 KB
testcase_79	AC	111 ms 54,296 KB
testcase_80	AC	112 ms 54,168 KB
testcase_81	AC	108 ms 53,932 KB
testcase_82	AC	108 ms 53,968 KB
testcase_83	AC	110 ms 53,188 KB
testcase_84	AC	106 ms 53,944 KB
testcase_85	AC	109 ms 53,948 KB
testcase_86	AC	137 ms 54,172 KB
testcase_87	AC	105 ms 53,920 KB
testcase_88	AC	106 ms 53,896 KB
testcase_89	AC	109 ms 53,836 KB
testcase_90	AC	109 ms 54,512 KB
testcase_91	AC	107 ms 54,004 KB
testcase_92	AC	111 ms 54,044 KB
testcase_93	AC	111 ms 53,936 KB
testcase_94	AC	132 ms 53,912 KB
testcase_95	AC	111 ms 53,672 KB
testcase_96	AC	108 ms 54,020 KB
testcase_97	AC	108 ms 53,944 KB
testcase_98	AC	108 ms 53,920 KB
testcase_99	AC	107 ms 54,508 KB

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

ソースコード

raw source code

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

/**
 * YukiCoder5015 2023/04/15 12:00～30h
 * @author tsukammo
 */
public class Main {

	// only call
	public static void main(String[] args) throws IOException {
		if (submit) {
			out = new PrintWriter(System.out);
			new Main().run();
			out.flush();
		} else {
			long scoreSum = 0;
			int startInd = 10;
			int testNum = 30;
			for (int i = startInd; i < startInd + testNum; i++) {
				file = new File(FILE_PATH + "out\\" + String.format("%04d", i) + ".txt");
				inFile = FILE_PATH + "in\\" + String.format("%04d", i) + ".txt";
				out = new PrintWriter(new BufferedWriter(new FileWriter(file)));
				long nst = System.nanoTime();
				Main m = new Main();
				m.run();
				out.flush();
				long net = System.nanoTime();
				int pastTime = (int) ((net - nst) / 1000000);
				System.err.println(i + "=" + scorePool + " T=" + pastTime);
				scoreSum += scorePool;
			}
			System.err.println("Sum=" + scoreSum);
			System.err.println("Ave=" + (scoreSum / testNum));
		}
	}

	// variables
	final static int N = 60;
	int Damege;
	final static int H = 1500;
	char[][] grid;
	boolean[][] block;
	int M;
	Enemy[] Enemies;

	List<Ans> answer;
	P Key, Goal, Start;

	int trueScore = -1;
	char bestColor = '-';
	char secondColor = '-';

	void run() {
		if (submit) {
			input();
		} else {
			scorePool = 0;
			inputFile(inFile);
		}
		init();
		solve();
		output();
	}

	long st;
	PriorityQueue<Node> nexts = new PriorityQueue<Node>();
	PriorityQueue<Node> tmp = new PriorityQueue<Node>(Collections.reverseOrder());
	int[][] distGrid = new int[N][N];

	// upsolve
	void solve() {
		// greedy
		int hp = H;
		P now = new P(Start);
		// まずは鍵まで移動
		calcDist(distGrid, Key);
		while (Key.dist(now) != 0) {
			int minD = distGrid[now.y][now.x];
			int tar = -1;
			for (int d = 0; d < 4; d++) {
				int nx = now.x + dx[d];
				int ny = now.y + dy[d];
				if (outGrid(nx, ny)) {
					continue;
				}
				if (block[ny][nx]) {
					continue;
				}
				if (minD > distGrid[ny][nx]) {
					minD = distGrid[ny][nx];
					tar = d;
				}
			}
			if (tar < 0) {
				System.err.println(hp);
				@SuppressWarnings("unused")
				int tmp = 1 / 0;
			}
			answer.add(new Ans(0, tar));
			now.x += dx[tar];
			now.y += dy[tar];
			hp--;
		}
		// ゴールまで移動
		calcDist(distGrid, Goal);
		while (Goal.dist(now) != 0) {
			int minD = distGrid[now.y][now.x];
			int tar = -1;
			for (int d = 0; d < 4; d++) {
				int nx = now.x + dx[d];
				int ny = now.y + dy[d];
				if (outGrid(nx, ny)) {
					continue;
				}
				if (block[ny][nx]) {
					continue;
				}
				if (minD > distGrid[ny][nx]) {
					minD = distGrid[ny][nx];
					tar = d;
				}
			}
			if (tar < 0) {
				@SuppressWarnings("unused")
				int tmp = 1 / 0;
			}
			answer.add(new Ans(0, tar));
			now.x += dx[tar];
			now.y += dy[tar];
		}
	}

	void calcDist(int[][] dist, P start) {
		for (int y = 0; y < N; y++) {
			Arrays.fill(dist[y], Integer.MAX_VALUE);
		}
		pq.clear();
		pq.add(start);
		dist[start.y][start.x] = 0;

		while (pq.size() > 0) {
			P p = pq.poll();
			int tmpD = dist[p.y][p.x];
			for (int d = 0; d < 4; d++) {
				int nx = p.x + dx[d];
				int ny = p.y + dy[d];
				if (outGrid(nx, ny)) {
					continue;
				}
				if (block[ny][nx]) {
					continue;
				}
				int nd = tmpD + 1;
				if (dist[ny][nx] > nd) {
					dist[ny][nx] = nd;
					pq.add(new P(nx, ny));
				}
			}
		}
	}

	void outboad(char[][] boad) {
		if (debug) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					System.err.print(boad[i][j]);
				}
				System.err.println();
			}
			System.err.println();
		}
	}

	int evalTrue(int score, int[] candyCount) {
		double ret = 1_000_000.0 * score;
		int sum = 0;
		for (int i = 0; i < candyCount.length; i++) {
			sum += Math.pow(candyCount[i], 2);
		}
		ret = ret / sum;
		int ret2 = (int) (Math.round(ret));
		return ret2;
	}

	void output() {
		try {
			Thread.sleep(1);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		StringBuilder buff = new StringBuilder();
		for (int i = 0; i < answer.size(); i++) {
			Ans a = answer.get(i);
			buff.append(a.toString());
			buff.append(ENT);
		}
		out.print(buff.toString());
		int score = 0;
		int trueScore = 0;
		if (debug || submit)
			System.err.println("Score = " + trueScore);
		scorePool = trueScore;
		if (debug) {
			System.err.println("Time = " + (System.currentTimeMillis() - st));
		}
	}

	ArrayDeque<P> pq = new ArrayDeque<>();

	boolean outGrid(int x, int y) {
		return x < 0 || y < 0 || x >= N || y >= N;
	}

	void init() {
		answer = new ArrayList<>();
		block = new boolean[N][N];
		// object の位置把握
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (grid[y][x] == 'G') {
					Goal = new P(x, y);
				} else if (grid[y][x] == 'K') {
					Key = new P(x, y);
				} else if (grid[y][x] == 'S') {
					Start = new P(x, y);
				} else if (grid[y][x] == '#') {
					block[y][x] = true;
				} else if (grid[y][x] == 'E') {
					block[y][x] = true;
				}
			}
		}
	}

	int eval(char[][] boad) {
		int ret = 0;
		return ret;
	}

	/**
	 * 素直に持つ
	 */
	void input() {
		in.nextInt(); //N
		st = System.currentTimeMillis();
		Damege = in.nextInt();
		in.next(); // H
		grid = new char[N][];
		for (int i = 0; i < N; i++) {
			char[] tmp = in.next().toCharArray();
			grid[i] = tmp;
		}
		M = in.nextInt();
		Enemies = new Enemy[M];
		for (int i = 0; i < M; i++) {
			int y = in.nextInt();
			int x = in.nextInt();
			int d = in.nextInt();
			Enemy e = new Enemy(i, x, y, d);
			Enemies[i] = e;
		}
		System.err.println("input end.");
	}

	List<String> lines;

	void inputFile(String path) {
		try {
			lines = Files.readAllLines(Paths.get(path), StandardCharsets.UTF_8);
			String[] line = lines.get(0).split(" ");
			st = System.currentTimeMillis();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	// predefined
	FastScanner in = new FastScanner(System.in);
	static PrintWriter out = new PrintWriter(System.out);
	static final String FILE_PATH = ".\\";
	static File file = new File(FILE_PATH + "output.txt");
	static String inFile = FILE_PATH + "in\\input_0.txt";
	static long scorePool = 0;
	public Random rnd = new Random(19881226L);
	static final int[] dx = new int[] { 1, 0, -1, 0 };
	static final int[] dy = new int[] { 0, 1, 0, -1 };
	static final String[] DIR_STR = new String[] { "R", "D", "L", "U" };
	static final String[] TYPE_STR = new String[] { "M", "B", "F" };
	static final int R = 0;
	static final int D = 1;
	static final int L = 2;
	static final int U = 3;
	static final char NONE = '-';

	static final int Depth = 1;
	static final String SPACE = " ";
	static final String ENT = "\r\n";

	// object
	class P {
		int x, y;

		public P(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public P(P p) {
			this.x = p.x;
			this.y = p.y;
		}

		public int dist(P p) {
			return (int) (Math.pow(x - p.x, 2) + Math.pow(y - p.y, 2));
		}

		public String toString() {
			return "(" + x + "," + y + ")";
		}
	}

	class Enemy extends P {
		int id;
		int d;

		public Enemy(int id, int x, int y, int d) {
			super(x, y);
			this.id = id;
			this.d = d;
		}
	}

	class Ans {
		int type;
		int dir;

		public Ans(int type, int dir) {
			this.type = type;
			this.dir = dir;
		}

		public String toString() {
			if (dir < 0) {
				return "S";
			}
			return TYPE_STR[type] + " " + DIR_STR[dir];
		}
	}

	class Node implements Comparable<Node> {

		char[][] boad;
		int score;

		public Node(char[][] boad, int out) {
			this.boad = new char[N][];
			for (int i = 0; i < N; i++) {
				this.boad[i] = Arrays.copyOf(boad[i], N);
			}
		}

		public Node(Node n) {
			this.boad = new char[N][];
			for (int i = 0; i < N; i++) {
				this.boad[i] = Arrays.copyOf(n.boad[i], N);
			}
		}

		// ソート用
		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.score, o.score);
		}
	}

	// library
	class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		FastScanner(InputStream in) {
			this.in = in;
		}

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		public boolean hasNext() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr]))
				ptr++;
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}

		public int nextInt() {
			long nl = nextLong();
			if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
				throw new NumberFormatException();
			return (int) nl;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}

	class Random {
		private long seed;
		private final long multiplier = 0x5DEECE66DL, addend = 0xBL, mask = (1L << 48) - 1;
		int bits, val;

		Random(long seed) {
			this.seed = seed;
		}

		int nextInt(int n) {
			do {
				bits = (int) ((seed = (seed * multiplier + addend) & mask) >>> 17);
				val = bits % n;
			} while (bits - val + (n - 1) < 0);
			return val;
		}

		double nextDouble() {
			return nextInt(10000000) / 10000000.0;
		}
	}

	static boolean debug = false;
	static boolean submit = true;
}

yukicoder

結果

テストケース

ソースコード