結果
| 問題 | No.1323 うしらずSwap |
| ユーザー |
 chocorusk
|
| 提出日時 | 2020-12-20 02:12:08 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,176 ms / 3,000 ms |
| コード長 | 6,400 bytes |
| コンパイル時間 | 1,880 ms |
| コンパイル使用メモリ | 149,812 KB |
| 最終ジャッジ日時 | 2025-01-17 04:21:18 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 59 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#include <list>#define popcount __builtin_popcountusing namespace std;typedef long long ll;typedef pair<int, int> P;int main(){int h, w;int ra, ca, rb, cb;cin>>h>>w>>ra>>ca>>rb>>cb;ra--;ca--;rb--;cb--;string s[1400];for(int i=0; i<h; i++){cin>>s[i];}const int INF=1e8;int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1};if(h<80 && w<80){int d[81][81][81][81];for(int i=0; i<h; i++){for(int j=0; j<w; j++){for(int k=0; k<h; k++){for(int l=0; l<w; l++){d[i][j][k][l]=INF;}}}}d[ra][ca][rb][cb]=0;using PP=pair<P, P>;queue<PP> que;que.push({{ra, ca}, {rb, cb}});while(!que.empty()){PP p=que.front(); que.pop();int xa=p.first.first, ya=p.first.second, xb=p.second.first, yb=p.second.second;for(int k=0; k<4; k++){int xa1=xa+dx[k], ya1=ya+dy[k];if(xa1==xb && ya1==yb) continue;if(s[xa1][ya1]!='#' && d[xa1][ya1][xb][yb]>d[xa][ya][xb][yb]+1){d[xa1][ya1][xb][yb]=d[xa][ya][xb][yb]+1;que.push({{xa1, ya1}, {xb, yb}});}}for(int k=0; k<4; k++){int xb1=xb+dx[k], yb1=yb+dy[k];if(xb1==xa && yb1==ya) continue;if(s[xb1][yb1]!='#' && d[xa][ya][xb1][yb1]>d[xa][ya][xb][yb]+1){d[xa][ya][xb1][yb1]=d[xa][ya][xb][yb]+1;que.push({{xa, ya}, {xb1, yb1}});}}}if(d[rb][cb][ra][ca]<INF) cout<<d[rb][cb][ra][ca]<<endl;else cout<<-1<<endl;return 0;}queue<P> que;que.push({ra, ca});int d[1400][1400];for(int i=0; i<h; i++){for(int j=0; j<w; j++){d[i][j]=INF;}}d[ra][ca]=0;while(!que.empty()){P p=que.front(); que.pop();int x=p.first, y=p.second;for(int k=0; k<4; k++){int x1=x+dx[k], y1=y+dy[k];if(s[x1][y1]!='#' && d[x1][y1]>d[x][y]+1){que.push({x1, y1});d[x1][y1]=d[x][y]+1;}}}int dr[1400][1400];for(int i=0; i<h; i++){for(int j=0; j<w; j++){dr[i][j]=INF;}}dr[rb][cb]=0;que.push({rb, cb});while(!que.empty()){P p=que.front(); que.pop();int x=p.first, y=p.second;for(int k=0; k<4; k++){int x1=x+dx[k], y1=y+dy[k];if(s[x1][y1]!='#' && dr[x1][y1]>dr[x][y]+1){que.push({x1, y1});dr[x1][y1]=dr[x][y]+1;}}}vector<P> v;for(int i=0; i<h; i++){for(int j=0; j<w; j++){if(s[i][j]!='#' && d[i][j]+dr[i][j]==d[rb][cb]){v.push_back({i, j});}}}if(v.size()>d[rb][cb]+1){cout<<2*d[rb][cb]<<endl;return 0;}int ans=INF;for(auto p:v){int x=p.first, y=p.second;for(int k=0; k<4; k++){int x1=x+dx[k], y1=y+dy[k];if(s[x1][y1]!='#' && dr[x1][y1]==d[rb][cb]-d[x][y]){ans=min(ans, 2*d[rb][cb]+1);}}}bool dame[1400][1400]={};for(auto p:v){int x=p.first, y=p.second;dame[x][y]=1;int cnt=0;for(int k=0; k<4; k++){int x1=x+dx[k], y1=y+dy[k];if(s[x1][y1]!='#'){cnt++;}}if(!(x==ra && y==ca) && !(x==rb && y==rb) && cnt>2){ans=min(ans, 2*d[rb][cb]+2);}}int e[1400][1400];for(int i=0; i<h; i++){for(int j=0; j<w; j++){e[i][j]=INF;}}e[ra][ca]=0;que.push({ra, ca});while(!que.empty()){P p=que.front(); que.pop();int x=p.first, y=p.second;for(int k=0; k<4; k++){int x1=x+dx[k], y1=y+dy[k];if(s[x1][y1]!='#' && (!dame[x1][y1] || !dame[x][y]) && e[x1][y1]>e[x][y]+1){que.push({x1, y1});e[x1][y1]=e[x][y]+1;}}}int e1[1400][1400];for(int i=0; i<h; i++){for(int j=0; j<w; j++){e1[i][j]=INF;}}e1[ra][ca]=0;que.push({ra, ca});while(!que.empty()){P p=que.front(); que.pop();int x=p.first, y=p.second;for(int k=0; k<4; k++){int x1=x+dx[k], y1=y+dy[k];if(s[x1][y1]!='#' && !dame[x1][y1] && e1[x1][y1]>e1[x][y]+1){que.push({x1, y1});e1[x1][y1]=e1[x][y]+1;}}}map<int, int> mp;for(int i=0; i<h; i++){for(int j=0; j<w; j++){mp[e1[i][j]]++;}}int mn=INF;for(auto p:mp){if(p.second>1){mn=min(mn, p.first);break;}}int er[1400][1400];for(int i=0; i<h; i++){for(int j=0; j<w; j++){er[i][j]=INF;}}er[rb][cb]=0;que.push({rb, cb});while(!que.empty()){P p=que.front(); que.pop();int x=p.first, y=p.second;for(int k=0; k<4; k++){int x1=x+dx[k], y1=y+dy[k];if(s[x1][y1]!='#' && !dame[x1][y1] && er[x1][y1]>er[x][y]+1){que.push({x1, y1});er[x1][y1]=er[x][y]+1;}}}map<int, int> mp2;for(int i=0; i<h; i++){for(int j=0; j<w; j++){mp2[er[i][j]]++;}}for(auto p:mp2){if(p.second>1){mn=min(mn, p.first);break;}}ans=min({ans, 2*d[rb][cb]+4*mn, d[rb][cb]+e[rb][cb]});if(ans<INF) cout<<ans<<endl;else cout<<-1<<endl;return 0;}