結果

問題 No.1323 うしらずSwap
ユーザー ei1333333
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0