https://atcoder.jp/contests/past202005-open/tasks/past202005_g
前提知識
解説
https://atcoder.jp/contests/past202005-open/submissions/14067221
さあ、この辺からギアが上がってくる感じがある。
コスト1の移動である地点からある地点への最短距離を求めると言えばBFSなので、
まずはBFSをベースに考えてみる。
考えるべき盤面の広さはどれだけだろうか。
縦も横も[-200,200]は入力があるので必要だろう。
それ以上は必要だろうか?
いや、必要ない。無駄に大回りになってしまうだけである。
本当か?
(200,200)がゴールで(199,200),(199,199),(200,199)に障害物があれば、迂回の必要があるぞ?
だが、それでも「大回り」をする必要はない。
よってちょっとした迂回分を入れた[-201,201]の広さの盤面でBFSすれば大丈夫。
正直、自分はあまりよく考えず[-250,250]くらいでやりました。
これで縦横で500×500くらいなので、これはBFSできる。
注意点としては配列に負数を入れる必要が出てくるので、BASEを使って0を250くらいにしておこう。
実装ヒントとして、遷移はゴリゴリ書くのではなく、dxdy記法を使うのがオススメ。
int N, X, Y; bool blocked[505][505]; const int MA = 500; const int BASE = 250; bool vis[505][505]; int mi[505][505]; int dx[6] = { 1, 0, -1, 1, -1, 0 }, dy[6] = { 1, 1, 1, 0, 0, -1 }; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> X >> Y; X += BASE; Y += BASE; rep(i, 0, N) { int x, y; cin >> x >> y; blocked[y + BASE][x + BASE] = true; } queue<pair<int, int>> que; que.push({ BASE, BASE }); vis[BASE][BASE] = true; while (!que.empty()) { int x, y; tie(x, y) = que.front(); que.pop(); rep(d, 0, 6) { int xx = x + dx[d]; int yy = y + dy[d]; if (0 <= xx && xx < MA && 0 <= yy && yy < MA) { if (blocked[yy][xx]) continue; if (vis[yy][xx]) continue; vis[yy][xx] = true; mi[yy][xx] = mi[y][x] + 1; que.push({ xx, yy }); } } } if (vis[Y][X]) cout << mi[Y][X] << endl; else cout << -1 << endl; }