結果
| 問題 |
No.1323 うしらずSwap
|
| コンテスト | |
| ユーザー |
 maine_honzuki
|
| 提出日時 | 2020-12-20 01:11:06 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 136 ms / 3,000 ms |
| コード長 | 6,499 bytes |
| コンパイル時間 | 2,457 ms |
| コンパイル使用メモリ | 212,360 KB |
| 最終ジャッジ日時 | 2025-01-17 04:16:26 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 59 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
int H, W, ax, ay, bx, by;
vector<string> S;
int main() {
cin >> H >> W >> ax >> ay >> bx >> by;
ax--;
ay--;
bx--;
by--;
S.resize(H);
for (int i = 0; i < H; i++) {
cin >> S[i];
for (auto& c : S[i])
if (c == '#')
c = 1;
else
c = 0;
}
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
queue<pair<int, pair<int, int>>> que;
que.push(make_pair(0, make_pair(ax, ay)));
vector<vector<int>> dist(H, vector<int>(W, -1));
dist[ax][ay] = 0;
que.push(make_pair(0, make_pair(ax, ay)));
while (!que.empty()) {
auto p = que.front();
que.pop();
int d = p.first, now_x = p.second.first, now_y = p.second.second;
if (now_x == bx && now_y == by)
continue;
for (int i = 0; i < 4; i++) {
int nxt_x = now_x + dx[i], nxt_y = now_y + dy[i];
if (S[nxt_x][nxt_y] == 1) {
continue;
}
if (dist[nxt_x][nxt_y] == -1) {
dist[nxt_x][nxt_y] = d + 1;
que.push(make_pair(d + 1, make_pair(nxt_x, nxt_y)));
}
}
}
if (dist[bx][by] == -1) {
cout << -1 << endl;
return 0;
}
bool flag1 = false, flag2 = false;
int now_x = bx, now_y = by, now_dist = dist[bx][by];
while (!(now_x == ax && now_y == ay)) {
int cnt1 = 0, cnt2 = 0, tmp_x, tmp_y;
for (int i = 0; i < 4; i++) {
int nxt_x = now_x + dx[i], nxt_y = now_y + dy[i];
if (dist[nxt_x][nxt_y] == now_dist - 1) {
cnt1++;
tmp_x = nxt_x;
tmp_y = nxt_y;
}
if (S[nxt_x][nxt_y] == 0)
cnt2++;
}
if (cnt1 >= 2)
flag1 = true;
if (now_dist != dist[bx][by])
if (cnt2 >= 3)
flag2 = true;
now_x = tmp_x;
now_y = tmp_y;
now_dist--;
}
if (flag1) {
cout << dist[bx][by] * 2 << endl;
} else if (flag2) {
cout << dist[bx][by] * 2 + 2 << endl;
} else {
int ans = 1e9;
//case 3
vector<int> d;
for (int i = 0; i < 4; i++) {
int tmp = dist[bx + dx[i]][by + dy[i]];
if (tmp != -1)
d.emplace_back(tmp);
}
sort(d.begin(), d.end());
if (d.size() >= 2) {
ans = min(ans, d[0] + d[1] + 2);
}
//case 1
for (int x = 1; x < H - 1; x++) {
for (int y = 1; y < W - 1; y++) {
if (dist[x][y] == -1)
continue;
int cnt = 0;
for (int i = 0; i < 4; i++) {
int nxt_x = x + dx[i], nxt_y = y + dy[i];
if (dist[nxt_x][nxt_y] == -1)
continue;
cnt += (dist[nxt_x][nxt_y] == dist[x][y] + 1);
}
if (dist[x][y] >= 1 && cnt >= 2)
ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4 + 4);
if (dist[x][y] == 0 && cnt >= 3)
ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4 + 4);
}
}
//case 4
for (int x = 1; x < H - 1; x++) {
for (int y = 1; y < W - 1; y++) {
if (dist[x][y] <= 0)
continue;
int cnt = 0;
for (int i = 0; i < 4; i++) {
int nxt_x = x + dx[i], nxt_y = y + dy[i];
if (dist[nxt_x][nxt_y] == -1)
continue;
cnt += (dist[nxt_x][nxt_y] == dist[x][y] - 1);
}
if (cnt >= 2)
ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4);
}
}
//case 2
{
swap(ax, bx);
swap(ay, by);
queue<pair<int, pair<int, int>>> que;
que.push(make_pair(0, make_pair(ax, ay)));
vector<vector<int>> dist(H, vector<int>(W, -1));
dist[ax][ay] = 0;
que.push(make_pair(0, make_pair(ax, ay)));
while (!que.empty()) {
auto p = que.front();
que.pop();
int d = p.first, now_x = p.second.first, now_y = p.second.second;
if (now_x == bx && now_y == by)
continue;
for (int i = 0; i < 4; i++) {
int nxt_x = now_x + dx[i], nxt_y = now_y + dy[i];
if (S[nxt_x][nxt_y] == 1) {
continue;
}
if (dist[nxt_x][nxt_y] == -1) {
dist[nxt_x][nxt_y] = d + 1;
que.push(make_pair(d + 1, make_pair(nxt_x, nxt_y)));
}
}
}
for (int x = 1; x < H - 1; x++) {
for (int y = 1; y < W - 1; y++) {
if (dist[x][y] == -1)
continue;
int cnt = 0;
for (int i = 0; i < 4; i++) {
int nxt_x = x + dx[i], nxt_y = y + dy[i];
if (dist[nxt_x][nxt_y] == -1)
continue;
cnt += (dist[nxt_x][nxt_y] == dist[x][y] + 1);
}
if (dist[x][y] >= 1 && cnt >= 2)
ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4 + 4);
if (dist[x][y] == 0 && cnt >= 3)
ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4 + 4);
}
}
for (int x = 1; x < H - 1; x++) {
for (int y = 1; y < W - 1; y++) {
if (dist[x][y] <= 0)
continue;
int cnt = 0;
for (int i = 0; i < 4; i++) {
int nxt_x = x + dx[i], nxt_y = y + dy[i];
if (dist[nxt_x][nxt_y] == -1)
continue;
cnt += (dist[nxt_x][nxt_y] == dist[x][y] - 1);
}
if (cnt >= 2)
ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4);
}
}
}
if (ans == (int)1e9)
ans = -1;
cout << ans << endl;
}
}