2013年 夏合宿4日目 Problem B : Trodden Cable [Licence: NYSL Version 0.9982]

Main.java

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;
        }
    }
}