結果

問題 No.124 門松列(3)
ユーザー Grenache
提出日時 2016-06-12 01:54:17
言語 Java
(openjdk 23)
結果
AC  
実行時間 127 ms / 5,000 ms
コード長 3,982 bytes
コンパイル時間 3,733 ms
コンパイル使用メモリ 80,408 KB
実行使用メモリ 41,728 KB
最終ジャッジ日時 2024-10-09 13:01:24
合計ジャッジ時間 7,106 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.*;
public class Main_yukicoder124 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Printer pr = new Printer(System.out);
        int w = sc.nextInt();
        int h = sc.nextInt();
        int[][] m = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                m[i][j] = sc.nextInt();
            }
        }
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        Queue<Integer> qx = new ArrayDeque<>();
        Queue<Integer> qy = new ArrayDeque<>();
        Queue<Integer> prev = new ArrayDeque<>();
        Queue<Integer> step = new ArrayDeque<>();
        List<List<Set<Integer>>> used = new ArrayList<>();
        for (int i = 0; i < h; i++) {
            List<Set<Integer>> tmp = new ArrayList<>();
            for (int j = 0; j < w; j++) {
                tmp.add(new HashSet<>());
            }
            used.add(tmp);
        }
        qx.add(0);
        qy.add(0);
        prev.add(enc(-1, -1, -1, -1));
        step.add(0);
        while (!qx.isEmpty()) {
            int x = qx.remove();
            int y = qy.remove();
            int p = prev.remove();
            int s = step.remove();
            int x1 = decx1(p);
            int y1 = decy1(p);
//          int x2 = decx2(p);
//          int y2 = decy2(p);
            if (x == w - 1 && y == h - 1) {
                pr.println(s);
                pr.close();
                sc.close();
                return;
            }
            for (int i = 0; i < dx.length; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= w || ny < 0 || ny >= h) {
                    continue;
                }
                if (x1 != 255) {
                    if (m[ny][nx] == m[y][x] || m[ny][nx] == m[y1][x1]) {
                        continue;
                    }
                    if (m[y][x] < m[y1][x1] && m[ny][nx] < m[y][x]) {
                        continue;
                    }
                    if (m[y][x] > m[y1][x1] && m[ny][nx] > m[y][x]) {
                        continue;
                    }
                }
                int ptmp = enc(x, y, x1, y1);
                if (used.get(ny).get(nx).contains(ptmp)) {
                    continue;
                }
                qx.add(nx);
                qy.add(ny);
                prev.add(ptmp);
                step.add(s + 1);
                used.get(ny).get(nx).add(ptmp);
            }
        }
        pr.println(-1);
        pr.close();
        sc.close();
    }
    private static int decx1(int p) {
        return (p >> 24) & 0xff;
    }
    private static int decy1(int p) {
        return (p >> 16) & 0xff;
    }
//  private static int decx2(int p) {
//      return (p >> 8) & 0xff;
//  }
//  private static int decy2(int p) {
//      return p & 0xff;
//  }
    private static int enc(int x1, int y1, int x2, int y2) {
        int ret = 0;
        ret |= x1 << 24;
        ret |= y1 << 16;
        ret |= x2 << 8;
        ret |= y2;
        return ret;
    }
    @SuppressWarnings("unused")
    private static class Scanner {
        BufferedReader br;
        Iterator<String> it;
        Scanner (InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String next() throws RuntimeException  {
            try {
                if (it == null || !it.hasNext()) {
                    it = Arrays.asList(br.readLine().split(" ")).iterator();
                }
                return it.next();
            } catch (IOException e) {
                throw new IllegalStateException();
            }
        }
        int nextInt() throws RuntimeException {
            return Integer.parseInt(next());
        }
        long nextLong() throws RuntimeException {
            return Long.parseLong(next());
        }
        float nextFloat() throws RuntimeException {
            return Float.parseFloat(next());
        }
        double nextDouble() throws RuntimeException {
            return Double.parseDouble(next());
        }
        void close() {
            try {
                br.close();
            } catch (IOException e) {
//              throw new IllegalStateException();
            }
        }
    }
    private static class Printer extends PrintWriter {
        Printer(PrintStream out) {
            super(out);
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0