結果
| 問題 | No.5015 Escape from Labyrinth |
| コンテスト | |
| ユーザー |
 tsukammo
|
| 提出日時 | 2023-04-15 13:46:16 |
| 言語 | Java (openjdk 23) |
| 結果 |
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 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
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;
}