結果
問題 | No.2928 Gridpath |
ユーザー | loop0919 |
提出日時 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | WA | - |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
ソースコード
#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; }