結果
| 問題 |
No.971 いたずらっ子
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:10:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,917 bytes |
| コンパイル時間 | 1,141 ms |
| コンパイル使用メモリ | 106,392 KB |
| 実行使用メモリ | 348,320 KB |
| 最終ジャッジ日時 | 2025-05-14 13:11:31 |
| 合計ジャッジ時間 | 8,059 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 4 |
| other | TLE * 1 -- * 20 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <tuple>
#include <vector> // Ensure vector is included
#include <limits> // Required for LLONG_MAX, though not strictly needed as we initialize distances only when first reaching a state
using namespace std;
// Define long long for potentially large time values
typedef long long ll;
// Using a map to store minimum distances found so far for each state.
// The key is a tuple representing the state: {row, column, mask}.
// The value is the minimum time (distance) to reach that state.
// Using map helps manage sparse states efficiently, where many mask combinations might not be reachable for a given cell.
map<tuple<int, int, int>, ll> dists;
// Define a min-priority queue.
// It stores pairs of {distance, state}. State is the tuple {row, column, mask}.
// We use std::greater to make it prioritize states with smaller distances.
priority_queue<pair<ll, tuple<int, int, int>>, vector<pair<ll, tuple<int, int, int>>>, greater<pair<ll, tuple<int, int, int>>>> pq;
int main() {
// Optimize C++ standard streams for faster input/output.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int H, W; // Grid dimensions: H rows (North-South), W columns (West-East)
cin >> H >> W;
vector<string> grid(H); // Stores the grid layout
vector<pair<int, int>> k_cells; // Stores coordinates {row, col} of all initial 'k' cells (0-based index)
// Maps a 'k' cell's coordinate pair {row, col} to a unique index from 0 to K-1.
// This index is used for the bitmask representation.
map<pair<int, int>, int> k_cell_indices;
// Read grid input and populate k_cells and k_cell_indices
for (int i = 0; i < H; ++i) {
cin >> grid[i];
for (int j = 0; j < W; ++j) {
if (grid[i][j] == 'k') {
k_cells.push_back({i, j}); // Store coordinates
k_cell_indices[{i, j}] = k_cells.size() - 1; // Assign index
}
}
}
int K = k_cells.size(); // Total number of initial 'k' cells
// Create the initial mask. If there are K 'k' cells, the mask is an integer with the first K bits set to 1.
// If K=0 (no 'k' cells), the mask is 0.
int initial_mask = (K == 0) ? 0 : (1 << K) - 1;
// Set up the initial state for Dijkstra's algorithm.
// Start at cell (0, 0) (which corresponds to problem's (1,1)), with the initial mask, and distance 0.
tuple<int, int, int> initial_state = {0, 0, initial_mask};
dists[initial_state] = 0; // Store distance 0 for the initial state
pq.push({0, initial_state}); // Push initial state onto the priority queue
// Define possible moves: South (down) and East (right).
// dr stores row changes, dc stores column changes.
int dr[] = {1, 0};
int dc[] = {0, 1};
// Dijkstra's algorithm main loop
while (!pq.empty()) {
// Extract the state with the smallest distance from the priority queue.
auto top = pq.top();
pq.pop();
ll d = top.first; // The minimum distance found so far to reach this state
tuple<int, int, int> current_state = top.second; // The state {row, column, mask}
int r, c, mask;
tie(r, c, mask) = current_state;
// Optimization: If the extracted distance 'd' is greater than the already known shortest distance
// to 'current_state', this means we found a shorter path earlier and already processed it (or it's currently
// in the map with a smaller value). So, we can skip this outdated entry.
// Uses map::find to check existence and access value without modifying map if key doesn't exist.
auto it = dists.find(current_state);
// Need check `it != dists.end()` primarily to handle case where state might somehow not be in map,
// but the core check is `d > it->second`. If `d == it->second`, it's the first time we extract this state with this distance.
if (it == dists.end() || d > it->second) {
continue;
}
// Check if we reached the target cell (H-1, W-1), which corresponds to (H, W) in problem statement.
if (r == H - 1 && c == W - 1) {
cout << d << endl; // Output the minimum time (distance)
return 0; // Successfully found the shortest path, exit program.
}
// Explore neighbors by trying possible moves (South and East)
for (int i = 0; i < 2; ++i) {
int nr = r + dr[i]; // Calculate next row coordinate
int nc = c + dc[i]; // Calculate next column coordinate
// Check if the next cell (nr, nc) is within the grid boundaries
if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
ll new_dist = d + 1; // Moving to a neighbor takes 1 minute.
bool is_k = false; // Flag to indicate if the next cell is an *active* 'k' cell
int k_idx = -1; // Index (0..K-1) of the 'k' cell, if it is one
// Check if the cell at (nr, nc) contains a 'k' character initially
if (grid[nr][nc] == 'k') {
// Find the index associated with this 'k' cell's coordinates
auto k_it = k_cell_indices.find({nr, nc});
// Check if the coordinate pair is indeed in our map of 'k' cells
if(k_it != k_cell_indices.end()){
k_idx = k_it->second; // Get the index
// Check if the bit corresponding to this index is set (1) in the current mask.
// If yes, this 'k' cell is currently active.
if ((mask >> k_idx) & 1) {
is_k = true;
}
}
// Note: If k_it == k_cell_indices.end(), something is wrong with data setup. Assume it's always found.
}
// Based on whether the next cell is an active 'k' cell, determine the next state.
if (is_k) {
// Scenario 1: Moved into an active 'k' cell.
// Player is teleported back to the start cell (0, 0).
int next_r = 0;
int next_c = 0;
// The mask is updated: the encountered 'k' cell is deactivated.
// This is done by flipping the corresponding bit from 1 to 0 using XOR.
int next_mask = mask ^ (1 << k_idx);
// Define the resulting state after teleportation and mask update.
tuple<int, int, int> next_state = {next_r, next_c, next_mask};
// Check if this path provides a shorter distance to 'next_state' than previously found.
auto dist_it = dists.find(next_state);
if (dist_it == dists.end() || new_dist < dist_it->second) {
// If it's the first time reaching this state, or if this path is shorter, update the distance.
dists[next_state] = new_dist;
// Push the new state and its distance onto the priority queue.
pq.push({new_dist, next_state});
}
} else {
// Scenario 2: Moved into a '.' cell or a 'k' cell that was already deactivated.
// Player moves normally to the cell (nr, nc).
int next_r = nr;
int next_c = nc;
// The mask remains unchanged since no active 'k' cell was encountered.
int next_mask = mask;
// Define the resulting state after the move.
tuple<int, int, int> next_state = {next_r, next_c, next_mask};
// Check if this path provides a shorter distance to 'next_state' than previously found.
auto dist_it = dists.find(next_state);
if (dist_it == dists.end() || new_dist < dist_it->second) {
// If it's the first time reaching this state, or if this path is shorter, update the distance.
dists[next_state] = new_dist;
// Push the new state and its distance onto the priority queue.
pq.push({new_dist, next_state});
}
}
}
}
}
// If the priority queue becomes empty and the target was not reached,
// this implies the target is unreachable. The problem statement guarantees
// start and end cells are not 'k', and allows movement South/East, suggesting
// reachability unless completely blocked. Assuming target is always reachable.
return 0; // Default return code, indicates successful execution.
}