迷路の最短路問題なので BFS でやりたくなるが、まともにやると 
で TLE してしまう！！
頂点の持ち方を工夫して 0-1 BFS で解く！
別解として枝刈り BFS も。
drken1215.hatenablog.com
問題概要
のグリッドが与えられます。各マスは通路 (文字 . で表される) と壁 (文字 # で表される) のいずれかです。
今あなたは座標 (Ax, Ay) にいます。ここから「ビショップの移動」を繰り返して座標 (Bx, By) に到達したいとします。そのための最小手数を答えてください。到達不可能な場合は -1 と出力してください。
なおビショップの移動とは「斜め四方向に、壁にぶつからない限りはどこまでも移動できる」というものです。壁を通り抜けたり、盤面外に出たりすることはできません。
制約
BFS では間に合わない
「迷路の最短路」は BFS の典型問題です。ただし通常の「迷路の最短路」問題では、1 回で移動できるマスが「上下左右に隣接する 4 マス」しかないのに対して、今回の問題では 1 回で 
個のマスに移動できうそうです。
BFS の計算量はグラフの辺数 
に対して 
です。1 回で移動できる箇所が となると、グラフの辺数は になります。よって単なる BFS だと、計算量は となって間に合いません。
ノードに「移動方向」を持たせて 1 マスずつ移動する
そこで、「1 回の移動で斜めにどこまでも進める」というのを次のように読み替えることにします。
- 各頂点が (縦方向座標, 横方向座標, 前回の移動方向) を表すグラフを考える
- 各頂点に対して斜め四方向に進んだ 4 マスにのみ辺を張る
- 移動方向が前回のものと一致するときは「辺のコスト：0」
- 移動方向が前回のものと異なるときは「辺のコスト：1」
こうしてできるグラフ上で、(Ax, Ay, 任意) を始点、(Bx, By, 任意) を終点とした最短経路問題を解けばよいことになります！！
こうしてグラフの辺数が 
で抑えられることになりました。ただし元々のグラフでは辺のコストがすべて 1 だとみなせたのに対して、今回は辺のコストは 0 と 1 がありうることになります。
普通の BFS ではダメなので、Dijkstra 法や 0-1 BFS を使います。
0-1 BFS
0-1 BFS は、辺のコストが 0, 1 のみに限ることを利用して、Dijkstra 法における priority_queue の部分を deque にすることで計算量を落とす手法です。Dijkstra 法の計算量 
が、0-1 BFS では 
に落ちます。
辺の重みが 0 と 1 のみに限られるとき、Dijkstra 法を回したときの priority_queue の中身は常に「最大値と最小値との差が 1 以下」という状態が保たれます。
よって、priority_queue の中身は高々 2 種類の値しか同時に共存しないことになります。priority_queue のような高級なデータ構造を使う必要はありません。代わりに
両端キュー deque を使う
という方法が考えられます。そして辺 
について緩和するとき、
- 辺のコストが 0 の場合：deque の先頭に push
- 辺のコストが 1 の場合：deque の末尾に push
というようにすればよいことになります。deque の両端に push する操作は 
でできるので、priority_queue を使うのに比べて計算量が落ちます。
今回の場合、計算量は になります。
コード
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const vector<int> dx = {1, 1, -1, -1};
const vector<int> dy = {1, -1, 1, -1};
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
int main() {
int N, Ax, Ay, Bx, By;
cin >> N >> Ax >> Ay >> Bx >> By;
--Ax, --Ay, --Bx, --By;
vector<string> S(N);
for (int i = 0; i < N; ++i) cin >> S[i];
vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(4, INF)));
deque<tuple<int,int,int>> que;
for (int dir = 0; dir < 4; ++dir) {
dp[Ax][Ay][dir] = 1;
que.push_back({Ax, Ay, dir});
}
while (!que.empty()) {
auto [x, y, dir] = que.front();
que.pop_front();
for (int ndir = 0; ndir < 4; ++ndir) {
int nx = x + dx[ndir], ny = y + dy[ndir];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (S[nx][ny] == '#') continue;
int cost = (ndir != dir);
if (chmin(dp[nx][ny][ndir], dp[x][y][dir] + cost)) {
if (cost == 0) que.push_front({nx, ny, ndir});
else que.push_back({nx, ny, ndir});
}
}
}
int res = INF;
for (int dir = 0; dir < 4; ++dir) chmin(res, dp[Bx][By][dir]);
cout << (res < INF ? res : -1) << endl;
}
別解：枝刈り BFS
さきほど、通常の BFS では TLE してしまうと書いたが、少し工夫することで通すことができる。
通常の BFS では、今いるマスから、斜め四方に壁にぶつからない限りどこまでも行く遷移を試す。
下のコードのような感じ。このコードは、移動方向 dir を決めた上で、その方向に壁にぶつかるまで遷移する様子を表している。
while (true) {
x += dx[dir], y += dy[dir];
if (x < 0 || x >= N || y < 0 || y >= N) break;
if (S[x][y] == '#') break;
if (chmin(dp[x][y], cur_dist + 1)) {
que.push({x, y});
}
}
枝刈り BFS は、次のように「もともとの距離値がより小さいようなマスに到達したら打ち切る」ようにするだけ！！！
while (true) {
x += dx[dir], y += dy[dir];
if (x < 0 || x >= N || y < 0 || y >= N) break;
if (S[x][y] == '#') break;
if (dp[x][y] < cur_dist + 1) break;
if (chmin(dp[x][y], cur_dist + 1)) {
que.push({x, y});
}
}
たったこれだけの工夫で劇的に早くなる。
コード
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const vector<int> dx = {1, 1, -1, -1};
const vector<int> dy = {1, -1, 1, -1};
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
int main() {
int N, Ax, Ay, Bx, By;
cin >> N >> Ax >> Ay >> Bx >> By;
--Ax, --Ay, --Bx, --By;
vector<string> S(N);
for (int i = 0; i < N; ++i) cin >> S[i];
vector<vector<int>> dp(N, vector<int>(N, INF));
queue<pair<int,int>> que;
dp[Ax][Ay] = 0;
que.push({Ax, Ay});
while (!que.empty()) {
auto [cx, cy] = que.front();
que.pop();
int cur_dist = dp[cx][cy];
for (int dir = 0; dir < 4; ++dir) {
int x = cx, y = cy;
while (true) {
x += dx[dir], y += dy[dir];
if (x < 0 || x >= N || y < 0 || y >= N) break;
if (S[x][y] == '#') break;
if (dp[x][y] < cur_dist + 1) break;
if (chmin(dp[x][y], cur_dist + 1)) {
que.push({x, y});
}
}
}
}
cout << (dp[Bx][By] < INF ? dp[Bx][By] : -1) << endl;
}
個のものから、いくつか選んだ結果を最適化する問題だということ
というように、思わせぶりであること
通り
