結果

提出番号	1017
提出者	yuki2006
言語	Java
提出日時	2017-08-11 02:21:00
問題名	(44)玉ねぎの収穫をするkotamanegi
結果	AC
点数	100%

---

テストケース

ソースコード

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Tuple implements Comparable<Tuple> {
    int x;
    int y;
    int value;

    Tuple(int x, int y, int value) {
        this.x = x;
        this.y = y;
        this.value = value;
    }

    @Override
    public int compareTo(Tuple o) {
        return Integer.compare(value, o.value);
    }
}

public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int H = scanner.nextInt();
        int W = scanner.nextInt();
        int y = scanner.nextInt() - 1;
        int x = scanner.nextInt() - 1;

        int[] yp = new int[H];
        for (int i = 0; i < H; i++) {
            yp[i] = scanner.nextInt();
        }

        int[] xp = new int[W];
        for (int i = 0; i < W; i++) {
            xp[i] = scanner.nextInt();
        }
        int yl = scanner.nextInt() - 1;
        int yr = scanner.nextInt() - 1;
        int xl = scanner.nextInt() - 1;
        int xr = scanner.nextInt() - 1;


        int[][] field = new int[H][W];
        for (int i = 0; i < H; i++) {
            Arrays.fill(field[i], Integer.MAX_VALUE);
        }

        PriorityQueue<Tuple> queue = new PriorityQueue<>();

        field[0][0] = 0;
        queue.add(new Tuple(0, 0, 0));
        while (!queue.isEmpty()) {
            Tuple current = queue.poll();

            for (int i = -1; i <= 1; i++) {
                final int nx = current.x + i;
                final int ny = current.y;
                final int nextValue = current.value + yp[current.y];

                if (0 <= nx && nx < W && 0 <= ny && ny < H) {
                    if (xl <= nx && nx <= xr && yl <= ny && ny <= yr) {
                        continue;
                    }
                    if (field[ny][nx] < nextValue) {
                        continue;
                    }

                    field[ny][nx] = nextValue;
                    queue.add(new Tuple(nx, ny, nextValue));
                }
            }
            for (int i = -1; i <= 1; i++) {
                final int nx = current.x;
                final int ny = current.y + i;
                final int nextValue = current.value + xp[nx];

                if (0 <= nx && nx < W && 0 <= ny && ny < H) {
                    if (xl <= nx && nx <= xr && yl <= ny && ny <= yr) {
                        continue;
                    }
                    if (field[ny][nx] < nextValue) {
                        continue;
                    }

                    field[ny][nx] = nextValue;
                    queue.add(new Tuple(nx, ny, nextValue));
                }
            }
        }
        final int ans = field[y][x];
        if (ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
}