結果
| 問題 |
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_popcount
using 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;
}