結果

問題 No.2928 Gridpath
ユーザー loop0919loop0919
提出日時 2024-09-13 17:17:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,398 bytes
コンパイル時間 942 ms
コンパイル使用メモリ 91,664 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-13 17:17:23
合計ジャッジ時間 3,621 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 4 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using namespace std;

int H, W;
int S_i, S_j, G_i, G_j;
int total_paths = 0;

// グリッドのサイズが最大 6x6 なので、ビットマスクで訪問状態を管理します
// ただし、再帰の深さが最大で 36 になるので、スタックオーバーフローの心配はありません
vector<vector<bool>> visited;

void dfs(int x, int y) {
    // ゴールに到達した場合、パスの数をインクリメント
    if (x == G_i && y == G_j) {
        total_paths++;
        return;
    }

    // 上下左右の移動
    const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {1, 0, -1, 0};

    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        // グリッドの範囲内か確認
        if (nx >= 0 && nx < H && ny >= 0 && ny < W) {
            // 訪問していない場合
            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                dfs(nx, ny);
                visited[nx][ny] = false; // バックトラック
            }
        }
    }
}

int main() {
    cin >> H >> W;
    cin >> S_i >> S_j;
    cin >> G_i >> G_j;

    // 0-index に調整
    S_i--; S_j--;
    G_i--; G_j--;

    visited.assign(H, vector<bool>(W, false));
    visited[S_i][S_j] = true;

    dfs(S_i, S_j);

    cout << total_paths << endl;

    return 0;
}
0