結果

問題 No.611 Day of the Mountain
ユーザー e869120
提出日時 2017-12-11 00:51:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,403 bytes
コンパイル時間 954 ms
コンパイル使用メモリ 79,856 KB
実行使用メモリ 356,096 KB
最終ジャッジ日時 2024-11-30 11:30:33
合計ジャッジ時間 3,139 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 9
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int H, W, a[1009][1009], p[1009][1009], res[1009][1009], mod = 201712111;
int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            char c; cin >> c;
            if (c == '?')a[i][j] = -1;
            else a[i][j] = (c - '0');
            p[i][j] = a[i][j];
        }
    }
    if (H < W) {
        for (int i = 0; i < max(H, W); i++) {
            for (int j = i + 1; j < max(H, W); j++) { swap(a[i][j], a[j][i]); swap(p[i][j], p[j][i]); }
        }
        swap(H, W);
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) { if (p[i][j] == -1)p[i][j] = 1; res[i][j] = 100009; }
    }
    res[0][0] = p[0][0];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (i == 0 && j == 0)continue;
            if (i != 0)res[i][j] = min(res[i][j], res[i - 1][j] + p[i][j]);
            if (j != 0)res[i][j] = min(res[i][j], res[i][j - 1] + p[i][j]);
        }
    }
    cout << res[H - 1][W - 1] << endl;
    vector<vector<vector<long long>>>dp(H + 1, vector<vector<long long>>(W + 1, vector<long long>((1 << W), 0LL)));
    dp[0][0][1] = 1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            for (int k = 0; k < (1 << W); k++) {
                if (dp[i][j][k] == 0)continue;
                int fx = i, fy = j + 1; if (fy == W) { fy = 0; fx++; }
                int bit[17]; for (int l = 0; l < W; l++) { if ((k&(1 << l)) != 0)bit[l] = 1; else bit[l] = 0; }
                bool U1 = true; if (j == 0)U1 = false; else { if (bit[j - 1] == 0)U1 = false; if (res[i][j - 1] + p[i][j] != res[i][j])U1 = false; }
                bool U2 = true; if (bit[j] == 0)U2 = false; else { if (res[i - 1][j] + p[i][j] != res[i][j])U2 = false; }
                if (a[i][j] == -1) {
                    if (U1 == true || U2 == true) {
                        dp[fx][fy][k | (1 << j)] += dp[i][j][k]; dp[fx][fy][k | (1 << j)] %= mod;
                        dp[fx][fy][k - bit[j] * (1 << j)] += dp[i][j][k] * 8LL; dp[fx][fy][k - bit[j] * (1 << j)] %= mod;
                    }
                    else {
                        dp[fx][fy][k - bit[j] * (1 << j)] += dp[i][j][k] * 9LL; dp[fx][fy][k - bit[j] * (1 << j)] %= mod;
                    }
                }
                else {
                    if (U1 == true || U2 == true) {
                        dp[fx][fy][k | (1 << j)] += dp[i][j][k]; dp[fx][fy][k | (1 << j)] %= mod;
                    }
                    else {
                        dp[fx][fy][k - bit[j] * (1 << j)] += dp[i][j][k] * 1LL; dp[fx][fy][k - bit[j] * (1 << j)] %= mod;
                    }
                }
            }
        }
    }
    long long ret = 0;
    for (int i = (1 << (W - 1)); i < (1 << W); i++)ret += dp[H][0][i];
    cout << ret % mod << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0