結果

問題 No.2708 Jewel holder
コンテスト
ユーザー futamegawa
提出日時 2024-03-31 14:14:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,692 bytes
コンパイル時間 1,064 ms
コンパイル使用メモリ 96,480 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-30 19:12:24
合計ジャッジ時間 1,677 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>

using namespace std;

const int MAX_H = 10;
const int MAX_W = 10;

int H, W;
vector<vector<char>> grid;
int count_paths = 0;

void dfs(int i, int j, int gems) {
    // マス(i, j)が右下のマス(H-1, W-1)であり、かつ宝石を没収されない経路であれば、経路の数をインクリメントする
    if (i == H - 1 && j == W - 1 && gems >= 0) {
        count_paths++;
        return;
    }

    // マス(i, j)がグリッドの範囲内であり、かつ壁(#)でない場合
    if (0 <= i && i < H && 0 <= j && j < W && grid[i][j] != '#') {
        // 右に進む
        if (j + 1 < W) {
            int new_gems = gems;
            if (grid[i][j + 1] == 'o') new_gems++;
            else if (grid[i][j + 1] == 'x') new_gems--;

            // 宝石が負の値になる場合は経路を無効にする
            if (new_gems >= 0) {
                dfs(i, j + 1, new_gems);
            }
        }
        // 下に進む
        if (i + 1 < H) {
            int new_gems = gems;
            if (grid[i + 1][j] == 'o') new_gems++;
            else if (grid[i + 1][j] == 'x') new_gems--;

            // 宝石が負の値になる場合は経路を無効にする
            if (new_gems >= 0) {
                dfs(i + 1, j, new_gems);
            }
        }
    }
}

int main() {
    cin >> H >> W;

    // グリッドの入力
    grid.resize(H, vector<char>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> grid[i][j];
        }
    }

    // 初期位置は(0, 0)で、宝石の初期個数は1つ
    dfs(0, 0, 1);

    cout << count_paths << endl;

    return 0;
}
0