結果
| 問題 |
No.228 ゆきこちゃんの 15 パズル
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:18:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 5,000 ms |
| コード長 | 9,366 bytes |
| コンパイル時間 | 1,337 ms |
| コンパイル使用メモリ | 105,328 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:19:49 |
| 合計ジャッジ時間 | 1,979 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <array>
#include <utility> // for std::pair
#include <functional> // for std::hash
// State representation for Breadth-First Search (BFS) queue
// Uses optimized memory by storing only essential information:
// hash, mask, and empty cell coordinates. The full grid is not stored.
struct State {
// 64-bit hash representing the entire 4x4 grid configuration.
// Each cell takes 4 bits (0-15), total 16 cells * 4 bits = 64 bits.
unsigned long long hash;
// Bitmask representing the set of tiles already moved.
// If the k-th bit is set, it means the tile with value k (1-15) has been moved once.
// Tile 0 (empty space) is not tracked.
int mask;
// Coordinates (row, column) of the empty cell (the cell containing value 0).
int empty_r, empty_c;
};
// Custom hash function for pairs of <unsigned long long, int>
// This is required for using std::pair as a key in std::unordered_set.
// The standard library doesn't provide a default hash function for pairs.
struct PairHash {
std::size_t operator()(const std::pair<unsigned long long, int>& p) const {
// Get hash values for the first and second elements of the pair.
auto hash1 = std::hash<unsigned long long>{}(p.first);
auto hash2 = std::hash<int>{}(p.second);
// Combine the two hash values.
// This specific combination logic is adapted from Boost library's hash_combine
// function, known for providing good distribution of hash values.
hash1 ^= hash2 + 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2);
return hash1;
}
};
// Constant representing 0xF (15 in decimal) as an unsigned long long.
// Used as a mask to extract 4 bits (representing a tile value from 0 to 15).
const unsigned long long MASK_15 = 0xF;
int main() {
// Optimize C++ standard stream I/O operations for speed.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Define the initial configuration of the 15 puzzle as a flat array.
// The standard initial state is 1 to 15 in order, with 0 (empty space) at the end.
std::array<int, 16> initial_tiles = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0};
// Initial position of the empty cell (0-based indexing).
int initial_empty_r = 3;
int initial_empty_c = 3;
// Read the target grid configuration from standard input.
// Compute the hash value for the target configuration simultaneously.
unsigned long long target_hash_val = 0;
std::array<int, 16> target_tiles; // Temporary storage for reading input tile values.
for (int i = 0; i < 16; ++i) {
std::cin >> target_tiles[i];
// Build the hash: Shift the current hash left by 4 bits and OR the new tile value.
// This effectively packs the 16 tile values into a 64-bit integer.
// The tile at index 0 (top-left) ends up in the most significant 4 bits,
// and the tile at index 15 (bottom-right) in the least significant 4 bits.
target_hash_val = (target_hash_val << 4) | target_tiles[i];
}
// Initialize the BFS queue.
std::queue<State> q;
// Initialize the visited set. It stores pairs of {grid hash, mask}.
// A state is considered visited if we have encountered the same grid configuration
// with the same set of used tiles before.
std::unordered_set<std::pair<unsigned long long, int>, PairHash> visited;
// Compute the hash for the initial grid configuration.
unsigned long long initial_hash_val = 0;
for (int i = 0; i < 16; ++i) {
initial_hash_val = (initial_hash_val << 4) | initial_tiles[i];
}
// Create the initial state object.
State initial_state;
initial_state.hash = initial_hash_val;
initial_state.mask = 0; // Initially, no tiles have been moved, so the mask is 0.
initial_state.empty_r = initial_empty_r;
initial_state.empty_c = initial_empty_c;
// Add the initial state to the queue and mark it as visited.
q.push(initial_state);
visited.insert({initial_hash_val, 0});
// Define relative coordinates for neighbors (Up, Down, Left, Right).
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
// Flag to indicate if the target state has been reached.
bool found = false;
// Start the BFS loop. Continue as long as the queue is not empty.
while (!q.empty()) {
// Dequeue the current state from the front of the queue.
State current_s = q.front();
q.pop();
// Check if the current grid configuration matches the target configuration.
// The mask value doesn't matter for the target check.
if (current_s.hash == target_hash_val) {
found = true; // Target configuration reached.
break; // Exit the BFS loop.
}
// Extract current state variables for easier access.
int r = current_s.empty_r;
int c = current_s.empty_c;
unsigned long long current_hash = current_s.hash;
int current_mask = current_s.mask;
// Explore the four neighbors of the empty cell.
for (int i = 0; i < 4; ++i) {
int nr = r + dr[i]; // Calculate neighbor row.
int nc = c + dc[i]; // Calculate neighbor column.
// Check if the neighbor coordinates are within the 4x4 grid bounds.
if (nr >= 0 && nr < 4 && nc >= 0 && nc < 4) {
// Calculate the linear index pk for the neighbor cell (nr, nc).
// Linear index maps (row, col) to 4*row + col, ranging from 0 to 15.
int pk = nr * 4 + nc;
// Extract the tile value k located at the neighbor cell from the current hash.
// The bit position calculation `4 * (15 - pk)` corresponds to the hash building logic.
int tile_k = (current_hash >> (4 * (15 - pk))) & MASK_15;
// Check if the tile k at the neighbor cell can be moved:
// 1. It must not be the empty cell itself (tile_k != 0).
// 2. The tile k must not have been moved previously. Check if the k-th bit in the mask is 0.
// The mask uses the tile value k (1-15) directly as the bit index.
if (tile_k != 0 && !((current_mask >> tile_k) & 1)) {
// Calculate the linear index p0 for the current empty cell (r, c).
int p0 = r * 4 + c;
// Calculate the hash of the next state efficiently using bitwise operations.
// This avoids reconstructing the grid or recalculating the hash from scratch.
// Create bitmasks to isolate the 4 bits corresponding to positions p0 and pk.
unsigned long long mask_p0_bits = (MASK_15 << (4 * (15 - p0)));
unsigned long long mask_pk_bits = (MASK_15 << (4 * (15 - pk)));
// Create the new hash value:
// Start with the current hash. Clear the 4 bits at positions p0 (empty cell) and pk (tile k).
unsigned long long next_hash = current_hash & (~mask_p0_bits) & (~mask_pk_bits);
// Set the 4 bits at position p0 (where empty cell was) to the value tile_k.
next_hash |= ((unsigned long long)tile_k << (4 * (15 - p0)));
// Set the 4 bits at position pk (where tile k was) to the value 0.
// Since the bits are already cleared to 0, no OR operation is needed.
// Calculate the mask for the next state by setting the k-th bit.
// This marks tile k as having been moved.
int next_mask = current_mask | (1 << tile_k);
// Check if the resulting state {next_hash, next_mask} has already been visited.
// The pair {hash value, mask value} uniquely identifies a visited state.
if (visited.find({next_hash, next_mask}) == visited.end()) {
// If this state has not been visited:
// 1. Add it to the visited set.
visited.insert({next_hash, next_mask});
// 2. Create the next state object.
State next_s;
next_s.hash = next_hash;
next_s.mask = next_mask;
// The empty cell moves to the neighbor's position (nr, nc).
next_s.empty_r = nr;
next_s.empty_c = nc;
// 3. Add the new state to the queue for further exploration.
q.push(next_s);
}
}
}
}
}
// After the BFS completes (or exits early if target found), output the result.
if (found) {
std::cout << "Yes" << std::endl; // Target configuration is reachable.
} else {
std::cout << "No" << std::endl; // Target configuration is not reachable.
}
return 0; // Indicate successful execution.
}