実装例
priority_queue
コストの小さい方から優先的に探索する為にpriority_queueを用いる。
// 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);
}
上下左右の探索
各方向への移動をまとめて処理する為のテクニック。
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方向の探索
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
}
}