結果
問題 | No.1323 うしらずSwap |
ユーザー |
![]() |
提出日時 | 2020-12-07 23:45:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 180 ms / 3,000 ms |
コード長 | 4,236 bytes |
コンパイル時間 | 2,490 ms |
コンパイル使用メモリ | 209,456 KB |
最終ジャッジ日時 | 2025-01-16 19:09:15 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#include <bits/stdc++.h>using namespace std;using pi = pair< int, int >;constexpr int inf = 1 << 30;constexpr int vy[] = {-1, 1, 0, 0};constexpr int vx[] = {0, 0, -1, 1};template< typename T, typename E >bool chmin(T &a, E b) {if(a > b) {a = b;return true;} else {return false;}}int main() {int H, W, Ya, Xa, Yb, Xb;cin >> H >> W >> Ya >> Xa >> Yb >> Xb;--Ya, --Xa, --Yb, --Xb;vector< string > S(H);for(auto &s : S) cin >> s;vector< vector< int > > min_cost(H, vector< int >(W, inf));vector< vector< int > > ways(H, vector< int >(W, 0));vector< vector< int > > from(H, vector< int >(W, -1));{queue< pi > que;min_cost[Ya][Xa] = 0;ways[Ya][Xa] = 1;que.emplace(Ya, Xa);while(!que.empty()) {auto[y, x] = que.front();que.pop();for(int k = 0; k < 4; k++) {int ny = y + vy[k];int nx = x + vx[k];if(S[ny][nx] == '#') continue;if(chmin(min_cost[ny][nx], min_cost[y][x] + 1)) {from[ny][nx] = k;ways[ny][nx] = 0;que.emplace(ny, nx);}if(min_cost[y][x] + 1 == min_cost[ny][nx]) {ways[ny][nx] += ways[y][x];chmin(ways[ny][nx], 2);}}}}if(ways[Yb][Xb] == 0) {cout << -1 << "\n";return 0;}if(ways[Yb][Xb] >= 2) {cout << min_cost[Yb][Xb] * 2 << "\n";return 0;}vector< pair< int, int > > path;int cy = Yb, cx = Xb;path.emplace_back(cy, cx);while(cy != Ya || cx != Xa) {int py = cy + vy[from[cy][cx] ^ 1];int px = cx + vx[from[cy][cx] ^ 1];cy = py;cx = px;path.emplace_back(cy, cx);}assert(min_cost[Yb][Xb] + 1 == path.size());for(auto &p : path) S[p.first][p.second] = '*';for(int i = 1; i + 1 < path.size(); i++) {for(int j = 0; j < 4; j++) {int ny = path[i].first + vy[j];int nx = path[i].second + vx[j];if(S[ny][nx] == '.') {cout << min_cost[Yb][Xb] * 2 + 2 << "\n";return 0;}}}int ret = inf;int pre = min_cost[Yb][Xb];{{queue< pi > que;min_cost[Yb][Xb] = 0;que.emplace(Yb, Xb);while(!que.empty()) {auto[y, x] = que.front();que.pop();for(int k = 0; k < 4; k++) {int ny = y + vy[k];int nx = x + vx[k];if(S[ny][nx] == '#') continue;if(chmin(min_cost[ny][nx], min_cost[y][x] + 1)) {que.emplace(ny, nx);}}}}for(int i = 1; i + 1 < H; i++) {for(int j = 1; j + 1 < W; j++) {if(S[i][j] == '.') {int deg = 0;for(int k = 0; k < 4; k++) {int ny = i + vy[k];int nx = j + vx[k];if(S[ny][nx] != '#') {++deg;}}if(deg >= 3 && min_cost[i][j] != inf) {chmin(ret, min_cost[i][j] * 4 + 4 + pre * 2);}}}}{int deg = 0;for(int k = 0; k < 4; k++) {int ny = Ya + vy[k];int nx = Xa + vx[k];if(S[ny][nx] == '.') {++deg;}}if(deg >= 2) {chmin(ret, 4 + pre * 2);}}{int deg = 0;for(int k = 0; k < 4; k++) {int ny = Yb + vy[k];int nx = Xb + vx[k];if(S[ny][nx] == '.') {++deg;}}if(deg >= 2) {chmin(ret, 4 + pre * 2);}}}{vector< vector< int > > min_cost2(H, vector< int >(W, inf));queue< pi > que;min_cost2[Ya][Xa] = 0;que.emplace(Ya, Xa);S[Ya][Xa] = '.';S[Yb][Xb] = '.';while(!que.empty()) {auto[y, x] = que.front();que.pop();for(int k = 0; k < 4; k++) {int ny = y + vy[k];int nx = x + vx[k];if(S[ny][nx] == '#' || S[ny][nx] == '*') continue;if(y == Ya && x == Xa && ny == Yb && nx == Xb) continue;if(chmin(min_cost2[ny][nx], min_cost2[y][x] + 1)) {que.emplace(ny, nx);}}}if(min_cost2[Yb][Xb] != inf) {chmin(ret, pre + min_cost2[Yb][Xb]);}}if(ret >= inf) ret = -1;cout << ret << "\n";}