結果

問題 No.3071 Double Speedrun
ユーザー tenten
提出日時 2025-03-27 17:43:46
言語 Java
(openjdk 23)
結果
AC  
実行時間 153 ms / 6,000 ms
コード長 5,394 bytes
コンパイル時間 2,634 ms
コンパイル使用メモリ 79,976 KB
実行使用メモリ 59,164 KB
最終ジャッジ日時 2025-03-27 17:43:53
合計ジャッジ時間 5,459 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    // 998244353 での剰余演算を行う
    static final long MOD = 998244353L;

    public static void main(String[] args) throws IOException {
        // 入力の高速化
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int height = Integer.parseInt(st.nextToken());
        int width = Integer.parseInt(st.nextToken());

        // グリッドの入力
        char[][] grid = new char[height][width];
        for (int i = 0; i < height; i++) {
            String line = br.readLine();
            grid[i] = line.toCharArray();
        }

        // 特殊ケース：高さまたは幅が2の場合は、全セルが通行可能なら答えは1、１つでも壁があれば0
        if (height == 2 || width == 2) {
            long result = 1;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (grid[i][j] == '#') {
                        result = 0;
                        break;
                    }
                }
            }
            System.out.println(result);
            return;
        }

        // 2×2の行列 mat の各成分を計算する
        long[][] mat = new long[2][2];

        // mat[0][0] : 先頭行を削除し、各行の末尾を削除したグリッドの最短経路数
        char[][] grid00 = subGrid(grid, true, false, false, true);
        long[][] dp00 = countLatticePath(grid00);
        mat[0][0] = dp00[grid00.length - 1][grid00[0].length - 1];

        // mat[0][1] : 先頭行と末尾行を削除したグリッドの最短経路数
        char[][] grid01 = subGrid(grid, true, true, false, false);
        long[][] dp01 = countLatticePath(grid01);
        mat[0][1] = dp01[grid01.length - 1][grid01[0].length - 1];

        // mat[1][0] : 各行の先頭と末尾を削除したグリッドの最短経路数
        char[][] grid10 = subGrid(grid, false, false, true, true);
        long[][] dp10 = countLatticePath(grid10);
        mat[1][0] = dp10[grid10.length - 1][grid10[0].length - 1];

        // mat[1][1] : 各行の先頭を削除し、末尾行を削除したグリッドの最短経路数
        char[][] grid11 = subGrid(grid, false, true, true, false);
        long[][] dp11 = countLatticePath(grid11);
        mat[1][1] = dp11[grid11.length - 1][grid11[0].length - 1];

        // 最終結果の計算： mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0] (mod MOD)
        long result = (mat[0][0] * mat[1][1] % MOD - mat[0][1] * mat[1][0] % MOD + MOD) % MOD;
        System.out.println(result);
    }

    /**
     * 格子状のグリッドにおいて、始点 (0,0) から各セルまでの最短経路数を動的計画法 (DP) で計算する
     * 通行不可のセルは '#' で表される
     *
     * @param grid 格子（2次元の文字配列）
     * @return 各セルまでの経路数を格納した 2 次元配列
     */
    static long[][] countLatticePath(char[][] grid) {
        int h = grid.length;
        int w = grid[0].length;
        long[][] dp = new long[h][w];

        // 始点が壁でなければ 1 をセット
        dp[0][0] = (grid[0][0] == '#' ? 0 : 1);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                // 壁の場合は経路数を計算しない
                if (grid[i][j] == '#') {
                    continue;
                }
                if (i == 0 && j == 0) {
                    continue;
                }
                long ways = 0;
                // 上から来る場合
                if (i > 0) {
                    ways = (ways + dp[i - 1][j]) % MOD;
                }
                // 左から来る場合
                if (j > 0) {
                    ways = (ways + dp[i][j - 1]) % MOD;
                }
                dp[i][j] = ways;
            }
        }
        return dp;
    }

    /**
     * グリッドの部分コピーを作成する
     *
     * @param grid 元のグリッド
     * @param removeFirstRow 最初の行を削除するか否か
     * @param removeLastRow 末尾の行を削除するか否か
     * @param removeFirstCol 各行の最初の要素を削除するか否か
     * @param removeLastCol 各行の末尾の要素を削除するか否か
     * @return 部分グリッド（新たな 2 次元文字配列）
     */
    static char[][] subGrid(char[][] grid, boolean removeFirstRow, boolean removeLastRow, boolean removeFirstCol, boolean removeLastCol) {
        int originalRows = grid.length;
        int originalCols = grid[0].length;
        int startRow = removeFirstRow ? 1 : 0;
        int endRow = removeLastRow ? originalRows - 1 : originalRows;
        int startCol = removeFirstCol ? 1 : 0;
        int endCol = removeLastCol ? originalCols - 1 : originalCols;
        int newRows = endRow - startRow;
        int newCols = endCol - startCol;
        char[][] sub = new char[newRows][newCols];
        for (int i = 0; i < newRows; i++) {
            for (int j = 0; j < newCols; j++) {
                sub[i][j] = grid[startRow + i][startCol + j];
            }
        }
        return sub;
    }
}
0