結果

問題 No.1638 Robot Maze
ユーザー ks2m
提出日時 2021-08-06 21:40:12
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,010 bytes
コンパイル時間 2,483 ms
コンパイル使用メモリ 78,184 KB
実行使用メモリ 50,588 KB
最終ジャッジ日時 2024-09-17 01:31:04
合計ジャッジ時間 7,510 ms
ジャッジサーバーID
(参考情報)
judge6 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 48 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int h = Integer.parseInt(sa[0]);
int w = Integer.parseInt(sa[1]);
sa = br.readLine().split(" ");
int[] cos = new int[4];
for (int i = 0; i < 4; i++) {
cos[i] = Integer.parseInt(sa[i]);
}
long k = Long.parseLong(sa[4]);
int p = Integer.parseInt(sa[5]);
sa = br.readLine().split(" ");
int xs = Integer.parseInt(sa[0]) - 1;
int ys = Integer.parseInt(sa[1]) - 1;
int xt = Integer.parseInt(sa[2]) - 1;
int yt = Integer.parseInt(sa[3]) - 1;
char[][] c = new char[h][w];
for (int i = 0; i < h; i++) {
c[i] = br.readLine().toCharArray();
}
br.close();
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int s = xs * w + ys;
long[] d = new long[h * w];
Arrays.fill(d, Long.MAX_VALUE);
d[s] = 0;
PriorityQueue<Node> que = new PriorityQueue<Node>();
Node first = new Node(s, 0);
que.add(first);
while (!que.isEmpty()) {
Node cur = que.poll();
if (cur.d > d[cur.v]) {
continue;
}
int cx = cur.v / w;
int cy = cur.v % w;
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx < 0 || h <= nx || ny < 0 || w <= ny || c[nx][ny] == '#') {
continue;
}
int next = nx * w + ny;
long alt = d[cur.v] + cos[i];
if (c[nx][ny] == '@') {
alt += p;
}
if (alt < d[next]) {
d[next] = alt;
que.add(new Node(next, alt));
}
}
}
if (d[xt * w + yt] <= k) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
static class Node implements Comparable<Node> {
int v;
long d;
public Node(int v, long d) {
this.v = v;
this.d = d;
}
public int compareTo(Node o) {
return Long.compare(d, o.d);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0