結果
| 問題 |
No.340 雪の足跡
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,997 bytes |
| コンパイル時間 | 1,062 ms |
| コンパイル使用メモリ | 89,440 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:01:28 |
| 合計ジャッジ時間 | 5,130 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 15 TLE * 1 -- * 16 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <utility> // Required for std::pair, though not directly used, good practice
#include <algorithm> // Required for std::min and std::max
using namespace std;
// Use int for distance. The maximum possible distance W*H-1 can be up to 10^6 - 1,
// which fits comfortably within a 32-bit signed integer.
const int INF = -1; // Use -1 to represent infinity or unreachable state.
int main() {
// Optimize C++ standard streams for faster I/O. Crucial for performance-sensitive problems.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int W, H; // Grid dimensions: Width W, Height H
cin >> W >> H;
int N; // Number of adults
cin >> N;
// Handle the edge case where the grid is 1x1.
// In this case, Mana's home (cell 0) is the same as Mitsuru's home (cell W*H-1 = 0).
// The distance is 0. We must still read the rest of the input to avoid errors.
if (W == 1 && H == 1) {
// Consume the remaining input lines describing adult paths.
for(int i = 0; i < N; ++i) {
int M; // Number of stops for adult i
cin >> M;
int dummy; // Variable to read and discard cell indices
// An adult i's path involves M+1 points: B_i,0 (start) to B_i,M (last stop).
for(int j = 0; j <= M; ++j) {
cin >> dummy; // Read and discard each B_i,j
}
}
cout << 0 << endl; // Output the distance 0
return 0; // Exit program
}
// Calculate the total number of cells in the grid. Use long long to prevent potential overflow if W*H is large, although W*H <= 10^6 fits in int.
long long total_cells = (long long)W * H;
// Data structures to store traversability of edges between adjacent cells.
// `can_pass_horizontal[h][w]` is true if Mana can pass between cell (w, h) and cell (w+1, h).
// Dimensions are H rows by (W-1) columns. Handle W=1 case by creating a vector of size 0.
vector<vector<bool>> can_pass_horizontal(H, vector<bool>(W > 1 ? W - 1 : 0, false));
// `can_pass_vertical[h][w]` is true if Mana can pass between cell (w, h) and cell (w, h+1).
// Dimensions are (H-1) rows by W columns. Handle H=1 case by creating a vector of size 0.
vector<vector<bool>> can_pass_vertical(H > 1 ? H - 1 : 0, vector<bool>(W, false));
// Process each adult's path to mark the edges they traverse as traversable for Mana.
for (int i = 0; i < N; ++i) {
int M; // Number of stops for adult i
cin >> M;
int prev_B; // Cell index where the adult was previously located
cin >> prev_B; // Read the starting cell B_i,0 for adult i
// An adult path consists of M segments: B_i,j -> B_i,j+1 for j=0..M-1
for (int j = 0; j < M; ++j) {
int curr_B; // Cell index where the adult stops next
cin >> curr_B; // Read the next stop B_i, j+1
// Convert cell indices to (w, h) coordinates
int prev_w = prev_B % W; // Previous column
int prev_h = prev_B / W; // Previous row
int curr_w = curr_B % W; // Current column
int curr_h = curr_B / W; // Current row
// Check if the move is vertical (same column)
if (prev_w == curr_w) {
// Only process vertical moves if H > 1 (grid has vertical dimension)
if (H > 1) {
int h_start = min(prev_h, curr_h); // Starting row index for the segment
int h_end = max(prev_h, curr_h); // Ending row index for the segment
// Mark all vertical edges along the path segment as traversable.
// The edge between (prev_w, h) and (prev_w, h+1) corresponds to can_pass_vertical[h][prev_w].
for (int h = h_start; h < h_end; ++h) {
// Basic boundary check for safety, though problem constraints should guarantee valid indices.
if (h >= 0 && h < H - 1 && prev_w >= 0 && prev_w < W) {
can_pass_vertical[h][prev_w] = true;
}
}
}
// Otherwise, the move must be horizontal (guaranteed by problem constraints)
} else {
// Only process horizontal moves if W > 1 (grid has horizontal dimension)
if (W > 1) {
int w_start = min(prev_w, curr_w); // Starting column index for the segment
int w_end = max(prev_w, curr_w); // Ending column index for the segment
// Mark all horizontal edges along the path segment as traversable.
// The edge between (w, prev_h) and (w+1, prev_h) corresponds to can_pass_horizontal[prev_h][w].
for (int w = w_start; w < w_end; ++w) {
// Basic boundary check for safety.
if (prev_h >= 0 && prev_h < H && w >= 0 && w < W - 1) {
can_pass_horizontal[prev_h][w] = true;
}
}
}
}
prev_B = curr_B; // Update the previous location for the next segment calculation
}
}
// Perform Breadth-First Search (BFS) to find the shortest path from cell 0 to cell W*H-1.
vector<int> dist(total_cells, INF); // Stores the shortest distance from cell 0 to each cell. Initialize with INF (-1).
queue<int> q; // Queue for BFS traversal. Stores cell indices.
// Start BFS from cell 0 (Mana's home) if the grid has cells.
if (total_cells > 0) {
dist[0] = 0; // Distance to starting cell is 0
q.push(0); // Add starting cell to the queue
}
int final_dist = INF; // Variable to store the shortest distance found to the destination.
// BFS main loop
while (!q.empty()) {
int u_idx = q.front(); // Get the current cell index from the front of the queue
q.pop(); // Remove it from the queue
// Check if we have reached the destination cell (Mitsuru's home at index W*H - 1)
if (u_idx == total_cells - 1) {
final_dist = dist[u_idx]; // Store the distance found
break; // Found the shortest path, exit BFS loop
}
// Get coordinates of the current cell
int u_w = u_idx % W;
int u_h = u_idx / W;
// Explore neighbors using the marked passages
// Check North neighbor: (u_w, u_h + 1)
// Requires H > 1 to have a North neighbor and possibility of vertical passages.
if (H > 1 && u_h + 1 < H) { // Check boundary: Is there a cell to the North?
// Check passage: Is vertical passage between (u_w, u_h) and (u_w, u_h+1) allowed?
// Passage information is stored at can_pass_vertical[u_h][u_w].
if (can_pass_vertical[u_h][u_w]) {
int v_idx = u_w + (u_h + 1) * W; // Calculate index of the North neighbor
if (dist[v_idx] == INF) { // If neighbor has not been visited yet
dist[v_idx] = dist[u_idx] + 1; // Update distance
q.push(v_idx); // Add neighbor to the queue
}
}
}
// Check South neighbor: (u_w, u_h - 1)
// Requires H > 1 for South neighbor / vertical passages.
if (H > 1 && u_h - 1 >= 0) { // Check boundary: Is there a cell to the South?
// Check passage: Is vertical passage between (u_w, u_h-1) and (u_w, u_h) allowed?
// Passage information is stored at can_pass_vertical[u_h - 1][u_w].
if (can_pass_vertical[u_h - 1][u_w]) {
int v_idx = u_w + (u_h - 1) * W; // Calculate index of the South neighbor
if (dist[v_idx] == INF) { // If neighbor not visited
dist[v_idx] = dist[u_idx] + 1;
q.push(v_idx);
}
}
}
// Check East neighbor: (u_w + 1, u_h)
// Requires W > 1 for East neighbor / horizontal passages.
if (W > 1 && u_w + 1 < W) { // Check boundary: Is there a cell to the East?
// Check passage: Is horizontal passage between (u_w, u_h) and (u_w+1, u_h) allowed?
// Passage information is stored at can_pass_horizontal[u_h][u_w].
if (can_pass_horizontal[u_h][u_w]) {
int v_idx = (u_w + 1) + u_h * W; // Calculate index of the East neighbor
if (dist[v_idx] == INF) { // If neighbor not visited
dist[v_idx] = dist[u_idx] + 1;
q.push(v_idx);
}
}
}
// Check West neighbor: (u_w - 1, u_h)
// Requires W > 1 for West neighbor / horizontal passages.
if (W > 1 && u_w - 1 >= 0) { // Check boundary: Is there a cell to the West?
// Check passage: Is horizontal passage between (u_w-1, u_h) and (u_w, u_h) allowed?
// Passage information is stored at can_pass_horizontal[u_h][u_w - 1].
if (can_pass_horizontal[u_h][u_w - 1]) {
int v_idx = (u_w - 1) + u_h * W; // Calculate index of the West neighbor
if (dist[v_idx] == INF) { // If neighbor not visited
dist[v_idx] = dist[u_idx] + 1;
q.push(v_idx);
}
}
}
}
// Output the final result based on whether the destination was reached.
if (final_dist != INF) {
cout << final_dist << endl; // Output the shortest distance found
} else {
// If destination is unreachable (and W*H > 1, because the W=1 H=1 case was handled earlier)
cout << "Odekakedekinai.." << endl; // Output the "cannot go out" message
}
return 0; // Indicate successful execution
}