Submission #2084296
Source Code Expand
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.io.PrintWriter;
public class Main {
static FastScanner sc = new FastScanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
public static final void main(String[] args) {
new Main().solve();
out.flush();
}
// ========================================================================= //
public void solve() {
sc.nextInt(); sc.nextInt(); sc.nextInt();
int s = 50;
int k = 2500;
int sy = sc.nextInt() - 1;
int sx = sc.nextInt() - 1;
int[][] board = new int[s][s];
for (int y = 0; y < s; y++) {
String row = sc.next();
for (int x = 0; x < s; x++) {
char c = row.charAt(x);
if (c == '#') board[y][x] = -1;
else board[y][x] = 0;
}
}
int n = sc.nextInt();
int[] F = new int[n + 1];
int[] D = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
board[sc.nextInt() - 1][sc.nextInt() - 1] = i;
F[i] = sc.nextInt();
D[i] = sc.nextInt();
}
ShortestPathSolver sps = new ShortestPathSolver(s);
StringBuilder ans = new StringBuilder();
int x = sx, y = sy;
int[][] costs = new int[s][s];
int[] path = new int[s * s];
LOOP:while (n >= 1 && ans.length() < k) {
int[] result = sps.bellmanford(board, costs, x, y);
int pathLen = sps.getPath(costs, x, y, result[0], result[1], path);
for (int i = 0; i < pathLen; i++) {
int nx = sps.x(path[i]);
int ny = sps.y(path[i]);
String dir = "";
if (nx - x == -1) {
dir = "L";
}
if (nx - x == 1) {
dir = "R";
}
if (ny - y == - 1) {
dir = "U";
}
if (ny - y == 1) {
dir = "D";
}
assert !dir.equals("");
if (ans.length() < k) ans.append(dir);
else break LOOP;
x = nx;
y = ny;
}
board[y][x] = 0;
n--;
assert y == result[1] && x == result[0];
}
while (ans.length() < k) {
ans.append("-");
}
System.out.println(ans.toString());
}
}
class ShortestPathSolver {
private final int n, mask;
private int[] queue;
public ShortestPathSolver(int n) {
this.n = n;
this.mask = (1 << 15) - 1;
this.queue = new int[n * n * 4];
}
// 単一始点複数終点
// 0: 通行可
// -1: 通行不可
// 1以上: 終点
public int[] bellmanford(int[][] board, int[][] costs, int sx, int sy) {
for (int i = 0; i < n; i++) Arrays.fill(costs[i], Integer.MAX_VALUE);
int headIdx = 0, tailIdx = 0, bs, ny, nx;
queue[tailIdx++] = p(sx, sy);
costs[sy][sx] = 0;
int minCost = Integer.MAX_VALUE;
int minCostP = -1;
while (headIdx != tailIdx) {
int p = queue[headIdx++];
int y = y(p);
int x = x(p);
int nextc = costs[y][x] + 1;
if (nextc >= minCost)
continue;
if (y >= 1 && nextc < costs[ny = y - 1][x]) {
if ((bs = board[ny][x]) > 0) {
minCost = nextc;
minCostP = p(x, ny);
costs[ny][x] = nextc;
}
else if (bs == 0) {
queue[tailIdx++] = p(x, ny);
costs[ny][x] = nextc;
}
}
if (x >= 1 && nextc < costs[y][nx = x - 1]) {
if ((bs = board[y][nx]) > 0) {
minCost = nextc;
minCostP = p(nx, y);
costs[y][nx] = nextc;
}
else if (bs == 0) {
queue[tailIdx++] = p(nx, y);
costs[y][nx] = nextc;
}
}
if (y < n - 1 && nextc < costs[ny = y + 1][x]) {
if ((bs = board[ny][x]) > 0) {
minCost = nextc;
minCostP = p(x, ny);
costs[ny][x] = nextc;
}
else if (bs == 0) {
queue[tailIdx++] = p(x, ny);
costs[ny][x] = nextc;
}
}
if (x < n - 1 && nextc < costs[y][nx = x + 1]) {
if ((bs = board[y][nx]) > 0) {
minCost = nextc;
minCostP = p(nx, y);
costs[y][nx] = nextc;
}
else if (bs == 0) {
queue[tailIdx++] = p(nx, y);
costs[y][nx] = nextc;
}
}
}
return new int[] {x(minCostP), y(minCostP)};
}
// 重みなしのパスを返す
// pathに終点からの最短経路を格納しパスの長さを返す
public int getPath(int[][] costs, int sx, int sy, int ex, int ey, int[] path) {
int pathLen = 0;
int x = ex, y = ey, nx, ny;
while (p(x, y) != p(sx, sy)) {
queue[pathLen++] = p(x, y);
int nextc = costs[y][x] - 1;
assert nextc >= 0;
if (y >= 1 && costs[ny = y - 1][x] == nextc) {
y = ny;
continue;
}
if (x >= 1 && costs[y][nx = x - 1] == nextc) {
x = nx;
continue;
}
if (y < n - 1 && costs[ny = y + 1][x] == nextc) {
y = ny;
continue;
}
if (x < n - 1 && costs[y][nx = x + 1] == nextc) {
x = nx;
}
}
int pathIdx = 0;
for (int i = pathLen - 1; i >= 0; i--) {
path[pathIdx++] = queue[i];
}
return pathLen;
}
public int p(int x, int y) { return (y << 15) | x; }
public int x(int p) { return p & mask; }
public int y(int p) { return (p >> 15); }
}
class FastScanner {
public static void main(String[] args) {
FastScanner f = new FastScanner(System.in);
while (true) {
System.out.println(f.nextInt());
}
}
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
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 static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; }
private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; }
private boolean hasNext() { skipUnprintable(); 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 String nextLine() {
if (!hasNext()) return null;
StringBuilder sb = new StringBuilder();
int b = readByte();
while (b != -1 && b != '\n') {
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 && '9' <= b) {
n *= 10;
n += b - '0';
}
else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
}
else {
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
if (!hasNext()) throw new NoSuchElementException();
int 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 FastScanner(String str) {
this(new ByteArrayInputStream(str.getBytes()));
}
public FastScanner(InputStream in) {
this.in = in;
}
}
Submission Info
Submission Time |
|
Task |
B - Food Collector |
User |
suikkee |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
14904 |
Code Size |
9983 Byte |
Status |
AC |
Exec Time |
88 ms |
Memory |
21844 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
1521 / 20000 |
1725 / 20000 |
1461 / 20000 |
1009 / 20000 |
1644 / 20000 |
1861 / 20000 |
1518 / 20000 |
1355 / 20000 |
1049 / 20000 |
1761 / 20000 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
84 ms |
20436 KB |
subtask_01_02.txt |
AC |
88 ms |
21716 KB |
subtask_01_03.txt |
AC |
85 ms |
21588 KB |
subtask_01_04.txt |
AC |
86 ms |
21460 KB |
subtask_01_05.txt |
AC |
86 ms |
19028 KB |
subtask_01_06.txt |
AC |
86 ms |
19668 KB |
subtask_01_07.txt |
AC |
84 ms |
18260 KB |
subtask_01_08.txt |
AC |
86 ms |
19796 KB |
subtask_01_09.txt |
AC |
84 ms |
21844 KB |
subtask_01_10.txt |
AC |
84 ms |
21716 KB |