実装例
priority_queue
コストの小さい方から優先的に探索する為にpriority_queueを用いる。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// cost, y, xの順 using tup = tuple<ll, int, int>; priority_queue<tup, vector<tup>, greater<tup>> q; // スタート地点を追加 q.emplace(0, sy, sx); while (!q.empty()) { auto t = q.top(); q.pop(); ll c = get<0>(t); int y = get<1>(t); int x = get<2>(t); // q.emplace(c + 1, ny, nx); } |
上下左右の探索
各方向への移動をまとめて処理する為のテクニック。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
constexpr int dy[4] = {0, 0, -1, +1}; constexpr int dx[4] = {-1, +1, 0, 0}; rep(i, 4) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny < 0 || ny >= h) continue; if (nx < 0 || nx >= w) continue; // do something } |
8方向の探索
|
1 2 3 4 5 6 7 8 9 10 11 |
for (int ny = y - 1; ny <= y + 1; ny++) { if (ny < 0 || ny >= h) continue; for (int nx = x - 1; nx <= x + 1; nx++) { if (nx < 0 || nx >= w) continue; // do something } } |