Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Created October 21, 2013 04:43
Show Gist options
  • Save hiroshi-cl/7078762 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/7078762 to your computer and use it in GitHub Desktop.
2013年 夏合宿4日目 Problem B : Trodden Cable [Licence: NYSL Version 0.9982]
import java.util.*;
public class Main {
private static final int[] dx = new int[128];
private static final int[] dy = new int[128];
private static final int[] dx2 = {0, 0, 1, -1};
private static final int[] dy2 = {-1, 1, 0, 0};
static {
dx['U'] = 0;
dy['U'] = -1;
dx['D'] = 0;
dy['D'] = 1;
dx['R'] = 1;
dy['R'] = 0;
dx['L'] = -1;
dy['L'] = 0;
}
public static void main(String... args) {
final Scanner sc = new Scanner(System.in);
final int W = sc.nextInt();
final int H = sc.nextInt();
final int N = sc.nextInt();
final int sx = 2 * sc.nextInt();
final int sy = 2 * sc.nextInt();
final int tx = 2 * sc.nextInt();
final int ty = 2 * sc.nextInt();
final int[][] map = new int[W * 2 + 1][H * 2 + 1];
for (int i = 0; i < N; i++) {
int x = 2 * sc.nextInt() + 1;
int y = 2 * sc.nextInt() + 1;
final int p = sc.nextInt();
final char[] cs = sc.next().toCharArray();
for (int j = 0; j < p; j++)
for (final char c : cs) {
final int mx = x + dx[c];
final int my = y + dy[c];
final int nx = x + 2 * dx[c];
final int ny = y + 2 * dy[c];
if (0 <= nx && nx <= 2 * W && 0 <= ny && ny <= 2 * H) {
map[mx][my]++;
x = nx;
y = ny;
}
}
}
final int[][] min = new int[W * 2 + 1][H * 2 + 1];
for (int i = 0; i <= 2 * W; i++)
for (int j = 0; j <= 2 * H; j++)
min[i][j] = Integer.MAX_VALUE;
min[sx][sy] = 0;
final Queue<Tuple> que = new PriorityQueue<>();
que.offer(new Tuple(0, sx, sy));
while (!que.isEmpty()) {
final Tuple t = que.poll();
if (t.x == tx && t.y == ty) {
System.out.println(t.key);
return;
}
if (min[t.x][t.y] < t.key)
continue;
for (int i = 0; i < 4; i++) {
final int mx = t.x + dx2[i];
final int my = t.y + dy2[i];
final int nx = t.x + 2 * dx2[i];
final int ny = t.y + 2 * dy2[i];
if (0 <= nx && nx <= 2 * W && 0 <= ny && ny <= 2 * H)
if (min[t.x][t.y] + map[mx][my] < min[nx][ny]) {
min[nx][ny] = min[t.x][t.y] + map[mx][my];
que.offer(new Tuple(min[nx][ny], nx, ny));
}
}
}
}
private static class Tuple implements Comparable<Tuple> {
final int key, x, y;
public Tuple(int key, int x, int y) {
this.key = key;
this.x = x;
this.y = y;
}
@Override
public int compareTo(Tuple o) {
return key == o.key ? x == o.x ? y - o.y : x - o.x : key - o.key;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment