Submission #1253855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253855		shawnchang51	Maze (JOI23_ho_t3)	C++17	0 / 100	0 ms	324 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];
}

// Helper function to find all reachable cells from given starts
auto bfsReachable = [&](const vector<pair<int, int>>& starts, vector<vector<bool>>& reachable) {
    queue<pair<int, int>> q;
    for (auto [x, y] : starts) {
        if (!reachable[x][y]) {
            reachable[x][y] = true;
            q.push({x, y});
        }
    }
    
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        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 && 
                !reachable[nx][ny] && grid[nx][ny] == '.') {
                reachable[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
};

// Find initially reachable cells (0 operations)
vector<vector<bool>> reachable(R, vector<bool>(C, false));
bfsReachable({{Sr, Sc}}, reachable);

if (reachable[Gr][Gc]) {
    cout << 0 << endl;
    return 0;
}

// Level-by-level BFS on number of operations
for (int ops = 1; ops <= 50; ops++) {
    vector<pair<int, int>> newStarts;
    vector<vector<bool>> used(R - N + 1, vector<bool>(C - N + 1, false));
    
    // Find all useful stamp positions for this level
    for (int a = 0; a <= R - N; a++) {
        for (int b = 0; b <= C - N; b++) {
            if (used[a][b]) continue;
            
            // Check if this stamp overlaps with currently reachable cells
            bool canUse = false;
            for (int i = a; i < a + N && !canUse; i++) {
                for (int j = b; j < b + N && !canUse; j++) {
                    if (reachable[i][j]) {
                        canUse = true;
                    }
                }
            }
            
            if (canUse) {
                used[a][b] = true;
                // Add all cells in this stamp as new starting points
                for (int i = a; i < a + N; i++) {
                    for (int j = b; j < b + N; j++) {
                        if (!reachable[i][j]) {
                            newStarts.push_back({i, j});
                        }
                    }
                }
            }
        }
    }
    
    // If no new starting points, we can't improve
    if (newStarts.empty()) break;
    
    // Expand reachability from new starting points
    bfsReachable(newStarts, reachable);
    
    if (reachable[Gr][Gc]) {
        cout << ops << endl;
        return 0;
    }
}

cout << -1 << endl; // Should not happen for valid inputs
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