結果
| 問題 |
No.1323 うしらずSwap
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:17:12 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 14,030 bytes |
| コンパイル時間 | 1,139 ms |
| コンパイル使用メモリ | 106,540 KB |
| 実行使用メモリ | 161,700 KB |
| 最終ジャッジ日時 | 2025-05-14 13:18:41 |
| 合計ジャッジ時間 | 6,793 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 TLE * 1 -- * 45 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <map> // Using map for storing distances. Keys are state representations.
#include <utility> // For pair
#include <algorithm> // For min
using namespace std;
// Type definitions for convenience
typedef long long ll; // Use long long for state representation key
typedef pair<int, int> pii; // Represents coordinates (row, col)
// Global variables
int H, W; // Grid dimensions
vector<string> S; // Grid layout storing '#' for obstacles and '.' for empty cells
ll N; // Total number of cells H * W, used for state encoding
// Directions for movement: up, down, left, right
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
// Convert a state represented by two positions (posA, posB) to a unique long long key.
// This is done by mapping each position (r, c) to a single index and then combining the two indices.
ll state_to_ll(pii posA, pii posB) {
// Convert 0-based (r, c) coordinates to a single index: row * W + col
ll idxA = (ll)posA.first * W + posA.second;
ll idxB = (ll)posB.first * W + posB.second;
// Combine two indices into a single key. N = H*W. Key = idxA * N + idxB.
// This ensures a unique key for each state ((rA, cA), (rB, cB)).
return idxA * N + idxB;
}
// Convert a long long key back to a state (pair of positions).
// This is the inverse operation of state_to_ll.
pair<pii, pii> ll_to_state(ll key) {
ll idxB = key % N; // Extract index of B
ll idxA = key / N; // Extract index of A
// Convert single indices back to (r, c) coordinates
pii posA = {(int)(idxA / W), (int)(idxA % W)}; // (row = index / W, col = index % W)
pii posB = {(int)(idxB / W), (int)(idxB % W)};
return {posA, posB};
}
// Check if coordinates (r, c) are within grid bounds and the cell is empty ('.').
// The problem guarantees the grid is surrounded by '#', so moving into boundary cells is naturally prevented.
// However, explicitly checking bounds is safer.
bool is_valid(int r, int c) {
return r >= 0 && r < H && c >= 0 && c < W && S[r][c] == '.';
}
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read input: grid dimensions H, W and initial positions (1-based)
int ra_start, ca_start, rb_start, cb_start;
cin >> H >> W >> ra_start >> ca_start >> rb_start >> cb_start;
N = (ll)H * W; // Calculate total number of cells
// Read grid layout
S.resize(H);
for (int i = 0; i < H; ++i) {
cin >> S[i];
}
// Adjust coordinates to 0-based indexing for internal calculations
pii start_A = {ra_start - 1, ca_start - 1};
pii start_B = {rb_start - 1, cb_start - 1};
// Target positions are the swapped initial positions
pii target_A = {rb_start - 1, cb_start - 1};
pii target_B = {ra_start - 1, ca_start - 1};
// Encode initial and target states into unique long long keys
ll initial_key = state_to_ll(start_A, start_B);
ll target_key = state_to_ll(target_A, target_B);
// If the initial state is already the target state, 0 moves are needed.
if (initial_key == target_key) {
cout << 0 << endl;
return 0;
}
// Data structures for Bidirectional BFS
map<ll, int> dist_f; // Stores distances from the initial state (forward search)
map<ll, int> dist_b; // Stores distances from the target state (backward search)
queue<ll> q_f; // Queue for states in the forward search frontier
queue<ll> q_b; // Queue for states in the backward search frontier
// Initialize forward search from the initial state
dist_f[initial_key] = 0;
q_f.push(initial_key);
// Initialize backward search from the target state
dist_b[target_key] = 0;
q_b.push(target_key);
int min_total_dist = -1; // Stores the minimum total distance found so far, initialized to -1 (unreachable)
// Main loop for Bidirectional BFS. Continues as long as both search frontiers are non-empty.
while (!q_f.empty() && !q_b.empty()) {
// Optimization: Check if the sum of minimum distances from both frontiers is already greater than or equal to the best path found.
// If so, no shorter path can be found, so we can terminate the search early.
if (min_total_dist != -1) {
// Get distance of states at the front of queues (these represent the minimum distances currently being explored)
int current_min_dist_f = dist_f[q_f.front()];
int current_min_dist_b = dist_b[q_b.front()];
if (current_min_dist_f + current_min_dist_b >= min_total_dist) {
break;
}
}
// Strategy: Expand the smaller frontier to keep the search balanced. This heuristic helps optimize performance.
if (q_f.size() <= q_b.size()) {
// Expand forward queue (q_f) for one level (all nodes at the current distance)
int current_level_size = q_f.size();
for(int i = 0; i < current_level_size; ++i) {
ll current_key = q_f.front(); // Get the current state key
q_f.pop(); // Remove it from the queue
pair<pii, pii> current_st = ll_to_state(current_key); // Decode key to positions
pii posA = current_st.first;
pii posB = current_st.second;
int d = dist_f[current_key]; // Current distance from the start state
// Check if this state has been reached by the backward search (meeting point found)
if (dist_b.count(current_key)) {
int total_dist = d + dist_b[current_key]; // Calculate total path distance
// Update minimum total distance if this path is shorter
if (min_total_dist == -1 || total_dist < min_total_dist) {
min_total_dist = total_dist;
}
}
// Pruning optimization: If the current path length `d` is already too large compared to the best path found,
// skip exploring neighbours from this state as it cannot lead to a shorter path.
if(min_total_dist != -1 && d >= min_total_dist) continue;
// Explore neighbors by trying to move A
for (int j = 0; j < 4; ++j) { // Iterate through 4 directions
int next_rA = posA.first + dr[j];
int next_cA = posA.second + dc[j];
pii next_posA = {next_rA, next_cA};
// Check validity of the move: within bounds, empty cell, and not occupied by B
if (is_valid(next_rA, next_cA) && next_posA != posB) {
ll next_key = state_to_ll(next_posA, posB); // Encode the new state
// If this neighbor state hasn't been visited yet in the forward search
if (!dist_f.count(next_key)) {
// Check distance limit before adding: if d+1 already reaches min_total_dist, no need to add.
if(min_total_dist != -1 && d + 1 >= min_total_dist) continue;
dist_f[next_key] = d + 1; // Record distance
q_f.push(next_key); // Add to the forward queue
// Immediately check if this new state meets the backward search frontier
if (dist_b.count(next_key)) {
int total_dist = d + 1 + dist_b[next_key];
if (min_total_dist == -1 || total_dist < min_total_dist) {
min_total_dist = total_dist;
}
}
}
}
}
// Explore neighbors by trying to move B
for (int j = 0; j < 4; ++j) { // Iterate through 4 directions
int next_rB = posB.first + dr[j];
int next_cB = posB.second + dc[j];
pii next_posB = {next_rB, next_cB};
// Check validity of the move: within bounds, empty cell, and not occupied by A
if (is_valid(next_rB, next_cB) && next_posB != posA) {
ll next_key = state_to_ll(posA, next_posB); // Encode the new state
// If this neighbor state hasn't been visited yet in the forward search
if (!dist_f.count(next_key)) {
// Check distance limit before adding
if(min_total_dist != -1 && d + 1 >= min_total_dist) continue;
dist_f[next_key] = d + 1; // Record distance
q_f.push(next_key); // Add to the forward queue
// Immediately check if this new state meets the backward search frontier
if (dist_b.count(next_key)) {
int total_dist = d + 1 + dist_b[next_key];
if (min_total_dist == -1 || total_dist < min_total_dist) {
min_total_dist = total_dist;
}
}
}
}
}
}
} else { // q_b size is smaller
// Expand backward queue (q_b) for one level
int current_level_size = q_b.size();
for(int i = 0; i < current_level_size; ++i) {
ll current_key = q_b.front(); // Get the current state key
q_b.pop(); // Remove it from the queue
pair<pii, pii> current_st = ll_to_state(current_key); // Decode key to positions
pii posA = current_st.first;
pii posB = current_st.second;
int d = dist_b[current_key]; // Current distance from the target state
// Check if this state has been reached by the forward search (meeting point found)
if (dist_f.count(current_key)) {
int total_dist = d + dist_f[current_key]; // Calculate total path distance
// Update minimum total distance if this path is shorter
if (min_total_dist == -1 || total_dist < min_total_dist) {
min_total_dist = total_dist;
}
}
// Pruning optimization similar to forward search
if(min_total_dist != -1 && d >= min_total_dist) continue;
// Explore neighbors by trying to move A (moves are reversible, same logic as forward)
for (int j = 0; j < 4; ++j) {
int next_rA = posA.first + dr[j];
int next_cA = posA.second + dc[j];
pii next_posA = {next_rA, next_cA};
if (is_valid(next_rA, next_cA) && next_posA != posB) {
ll next_key = state_to_ll(next_posA, posB); // Encode the new state
// If this neighbor state hasn't been visited yet in the backward search
if (!dist_b.count(next_key)) {
// Check distance limit before adding
if(min_total_dist != -1 && d + 1 >= min_total_dist) continue;
dist_b[next_key] = d + 1; // Record distance
q_b.push(next_key); // Add to the backward queue
// Immediately check if this new state meets the forward search frontier
if (dist_f.count(next_key)) {
int total_dist = d + 1 + dist_f[next_key];
if (min_total_dist == -1 || total_dist < min_total_dist) {
min_total_dist = total_dist;
}
}
}
}
}
// Explore neighbors by trying to move B
for (int j = 0; j < 4; ++j) {
int next_rB = posB.first + dr[j];
int next_cB = posB.second + dc[j];
pii next_posB = {next_rB, next_cB};
if (is_valid(next_rB, next_cB) && next_posB != posA) {
ll next_key = state_to_ll(posA, next_posB); // Encode the new state
// If this neighbor state hasn't been visited yet in the backward search
if (!dist_b.count(next_key)) {
// Check distance limit before adding
if(min_total_dist != -1 && d + 1 >= min_total_dist) continue;
dist_b[next_key] = d + 1; // Record distance
q_b.push(next_key); // Add to the backward queue
// Immediately check if this new state meets the forward search frontier
if (dist_f.count(next_key)) {
int total_dist = d + 1 + dist_f[next_key];
if (min_total_dist == -1 || total_dist < min_total_dist) {
min_total_dist = total_dist;
}
}
}
}
}
}
}
}
// Output the minimum total distance found. If no path was found, min_total_dist remains -1.
cout << min_total_dist << endl;
return 0;
}