結果

問題 No.2657 Falling Block Game
ユーザー ks2m
提出日時 2024-03-01 23:00:29
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,697 bytes
コンパイル時間 2,524 ms
コンパイル使用メモリ 86,856 KB
実行使用メモリ 119,568 KB
最終ジャッジ日時 2024-09-29 14:47:32
合計ジャッジ時間 9,517 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

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

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();
        int inf = 100000000;
        int[][] d = new int[h][w];
        for (int i = 0; i < h; i++) {
            Arrays.fill(d[i], inf);
        }
        List<TreeSet<Integer>> list = new ArrayList<>(h - 1);
        for (int i = 0; i < h - 1; i++) {
            TreeSet<Integer> set = new TreeSet<>();
            for (int j = 0; j < w; j++) {
                set.add(j);
            }
            list.add(set);
        }
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.d - o2.d);
        int h1 = h - 1;
        for (int j = 0; j < w; j++) {
            if (s[h1][j] == '.') {
                d[h1][j] = 0;
                que.add(new Obj(h1, j, d[h1][j]));
            }
        }
        List<Integer> remList = new ArrayList<>();
        while (!que.isEmpty()) {
            Obj o = que.poll();
            if (d[o.i][o.j] < o.d) {
                continue;
            }
            if (o.i > 0 && s[o.i - 1][o.j] == '.') {
                int ni = o.i - 1;
                int end = Math.min(o.j + o.d, w - 1);
                TreeSet<Integer> set = list.get(ni);
                Set<Integer> ss = set.subSet(o.j, true, end, true);
                for (int nj : ss) {
                    if (s[ni][nj] == '#') {
                        break;
                    }
                    int alt = o.d;
                    if (d[ni][nj] > alt) {
                        d[ni][nj] = alt;
                        que.add(new Obj(ni, nj, alt));
                    }
                    remList.add(nj);
                }
                set.removeAll(remList);
                remList.clear();
                end = Math.max(o.j - o.d, 0);
                ss = list.get(ni).subSet(end, true, o.j, true).descendingSet();
                for (int nj : ss) {
                    if (s[ni][nj] == '#') {
                        break;
                    }
                    int alt = o.d;
                    if (d[ni][nj] > alt) {
                        d[ni][nj] = alt;
                        que.add(new Obj(ni, nj, alt));
                    }
                    remList.add(nj);
                }
                set.removeAll(remList);
                remList.clear();
            }
            int ni = o.i;
            if (o.j > 0) {
                int nj = o.j - 1;
                if (s[ni][nj] == '.') {
                    int alt = o.d + 1;
                    if (d[ni][nj] > alt) {
                        d[ni][nj] = alt;
                        que.add(new Obj(ni, nj, alt));
                    }
                }
            }
            if (o.j < w - 1) {
                int nj = o.j + 1;
                if (s[ni][nj] == '.') {
                    int alt = o.d + 1;
                    if (d[ni][nj] > alt) {
                        d[ni][nj] = alt;
                        que.add(new Obj(ni, nj, alt));
                    }
                }
            }
        }
        PrintWriter pw = new PrintWriter(System.out);
        for (int j = 0; j < w; j++) {
            pw.println(d[0][j]);
        }
        pw.flush();
    }
    static class Obj {
        int i, j, d;
        public Obj(int i, int j, int d) {
            this.i = i;
            this.j = j;
            this.d = d;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0