結果
問題 | No.1323 うしらずSwap |
ユーザー |
![]() |
提出日時 | 2020-12-20 15:27:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,465 ms / 3,000 ms |
コード長 | 5,946 bytes |
コンパイル時間 | 1,373 ms |
コンパイル使用メモリ | 105,140 KB |
最終ジャッジ日時 | 2025-01-17 04:52:19 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <set>#include <map>#include <cassert>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;const int INF = 1e+9;typedef pair<int, int> P;struct edge{int to;int cost;};void dijkstra(int s, int num_v, vector<edge> G[], int d[]){priority_queue<P, vector<P>, greater<P>> que;fill(d, d+num_v, INF);d[s] = 0;que.push(P(0, s));while(!que.empty()){P p = que.top();que.pop();int v = p.second;if(d[v] < p.first) continue;for(int i = 0; i < G[v].size(); i++){edge e = G[v][i];if(d[v] + e.cost < d[e.to]){d[e.to] = d[v] + e.cost;que.push(P(d[e.to], e.to));}}}}int h, w, ra, ca, rb, cb;char s[1500][1500];int dh[4] = {0, 0, -1, 1};int dw[4] = {-1, 1, 0, 0};bool is_in_field(int i, int j){return i >= 0 && i < h && j >= 0 && j < w;}int to_idx(int i, int j){return i*w+j;}int to_i(int idx){return idx/w;}int to_j(int idx){return idx%w;}void input(){cin >> h >> w >> ra >> ca >> rb >> cb;ra--; ca--; rb--; cb--;for(int i = 0; i < h; i++){for(int j = 0; j < w; j++){cin >> s[i][j];}}}vector<edge> G[1333*1333];int dist[1333*1333];vector<P> get_shortest_path(){int cur_h = rb, cur_w = cb;vector<P> ans;ans.push_back(P(cur_h, cur_w));while(cur_h != ra || cur_w != ca){for(int i = 0; i < 4; i++){int h_to = cur_h+dh[i];int w_to = cur_w+dw[i];if(is_in_field(h_to, w_to) && dist[to_idx(h_to, w_to)] == dist[to_idx(cur_h, cur_w)]-1){cur_h = h_to;cur_w = w_to;break;}}ans.push_back(P(cur_h, cur_w));}return ans;}vector<edge> G_rem[1333*1333];bool used_in_path[1333][1333];void make_g_rem(){for(int i = 0; i < h; i++){for(int j = 0; j < w; j++){if(s[i][j] == '#') continue;for(int k = 0; k < 4; k++){int i_to = i+dh[k], j_to = j+dw[k];if(is_in_field(i_to, j_to) && s[i_to][j_to] == '.'){if(used_in_path[i][j] && used_in_path[i_to][j_to]) continue;G_rem[to_idx(i, j)].push_back((edge){to_idx(i_to, j_to), 1});}}}}}// 三箇所と繋がっているところまでの距離int calc_dist_three(int from){vector<int> dist(h*w, INF);queue<int> que;dist[from] = 0;que.push(from);while(!que.empty()){int v = que.front(); que.pop();int cnt = 0;int i = to_i(v), j = to_j(v);assert(s[i][j] == '.');for(int k = 0; k < 4; k++){int i_to = i+dh[k], j_to = j+dw[k];if(is_in_field(i_to, j_to) && s[i_to][j_to] == '.'){cnt++;if(dist[to_idx(i_to, j_to)] == INF){dist[to_idx(i_to, j_to)] = dist[v]+1;que.push(to_idx(i_to, j_to));}}}if(cnt >= 3){return dist[v];}}return INF;}int dist_rem[1333*1333];void solve(){for(int i = 0; i < h; i++){for(int j = 0; j < w; j++){if(s[i][j] == '#') continue;for(int k = 0; k < 4; k++){int i_to = i+dh[k], j_to = j+dw[k];if(is_in_field(i_to, j_to) && s[i_to][j_to] == '.'){G[to_idx(i, j)].push_back((edge){to_idx(i_to, j_to), 1});}}}}dijkstra(to_idx(ra, ca), h*w, G, dist);if(dist[to_idx(rb, cb)] == INF){cout << -1 << endl;return;}vector<P> path = get_shortest_path();for(auto p : path){used_in_path[p.first][p.second] = true;// cout << p.first << ',' << p.second << endl;}make_g_rem();// dijkstraっぽい感じint min_diff = INF;priority_queue<P, vector<P>, greater<P>> que;fill(dist_rem, dist_rem+h*w, INF);for(auto p : path){int idx = to_idx(p.first, p.second);dist_rem[idx] = dist[idx];if(p.first == rb && p.second == cb) continue;que.push(P(dist[idx], idx));}while(!que.empty()){P p = que.top();que.pop();int v = p.second;if(dist_rem[v] < p.first) continue;for(int i = 0; i < G_rem[v].size(); i++){edge e = G_rem[v][i];if(dist_rem[v] + e.cost < dist_rem[e.to] && e.to != to_idx(rb, cb)){dist_rem[e.to] = dist_rem[v] + e.cost;que.push(P(dist_rem[e.to], e.to));}if(used_in_path[to_i(e.to)][to_j(e.to)] && e.to != to_idx(ra, ca)){chmin(min_diff, dist_rem[v] + e.cost - dist_rem[e.to]);// cout << to_i(v) << ',' << to_j(v) << ' ' << to_i(e.to) << ',' << to_j(e.to) << endl;}}}assert(min_diff >= 0);int tmp = calc_dist_three(to_idx(ra, ca));if(tmp != INF) chmin(min_diff, 4*(tmp+1));tmp = calc_dist_three(to_idx(rb, cb));if(tmp != INF) chmin(min_diff, 4*(tmp+1));if(min_diff == INF){cout << -1 << endl;}else{cout << 2*dist[to_idx(rb, cb)]+min_diff << endl;}}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;input();solve();}