Submission #1253856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253856		shawnchang51	Maze (JOI23_ho_t3)	C++17	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int R, C, N;
cin >> R >> C >> N;

int Sr, Sc, Gr, Gc;
cin >> Sr >> Sc >> Gr >> Gc;
Sr--; Sc--; Gr--; Gc--;  // Convert to 0-indexed

vector<string> grid(R);
for (int i = 0; i < R; i++) {
    cin >> grid[i];
}

// 0-1 BFS with distance tracking
vector<vector<int>> dist(R, vector<int>(C, INT_MAX));
vector<vector<bool>> processed(R, vector<bool>(C, false));
deque<pair<int, int>> dq;

dist[Sr][Sc] = 0;
dq.push_back({Sr, Sc});

while (!dq.empty()) {
    auto [x, y] = dq.front();
    dq.pop_front();
    
    // Skip if already processed
    if (processed[x][y]) continue;
    processed[x][y] = true;
    
    // Early termination if we reached the goal
    if (x == Gr && y == Gc) {
        break;
    }
    
    // Move to adjacent white cells (cost 0)
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx >= 0 && nx < R && ny >= 0 && ny < C && 
            grid[nx][ny] == '.' && dist[nx][ny] > dist[x][y]) {
            dist[nx][ny] = dist[x][y];
            dq.push_front({nx, ny});  // Cost 0, add to front
        }
    }
    
    // Apply stamp (cost 1)
    // Find all valid stamp positions that include (x, y)
    int a_min = max(0, x - N + 1);
    int a_max = min(R - N, x);
    int b_min = max(0, y - N + 1);
    int b_max = min(C - N, y);
    
    for (int a = a_min; a <= a_max; a++) {
        for (int b = b_min; b <= b_max; b++) {
            // Stamp at (a, b) covers cells [a, a+N) × [b, b+N)
            for (int i = a; i < min(R, a + N); i++) {
                for (int j = b; j < min(C, b + N); j++) {
                    if (dist[i][j] > dist[x][y] + 1) {
                        dist[i][j] = dist[x][y] + 1;
                        dq.push_back({i, j});  // Cost 1, add to back
                    }
                }
            }
        }
    }
}

cout << dist[Gr][Gc] << endl;
return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6