Submission #1253852

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

// Check if goal is reachable
auto canReach = [&](const vector<string>& g) -> bool {
    vector<vector<bool>> visited(R, vector<bool>(C, false));
    queue<pair<int, int>> q;
    q.push({Sr, Sc});
    visited[Sr][Sc] = true;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        if (x == Gr && y == Gc) return true;
        
        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 && 
                !visited[nx][ny] && g[nx][ny] == '.') {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    return false;
};

if (canReach(grid)) {
    cout << 0 << endl;
    return 0;
}

// Generate all possible stamp positions
vector<pair<int, int>> stamps;
for (int a = 0; a <= R - N; a++) {
    for (int b = 0; b <= C - N; b++) {
        stamps.push_back({a, b});
    }
}

int numStamps = stamps.size();

// BFS on stamp combinations
for (int ops = 1; ops <= min(20, numStamps); ops++) {
    // Try all combinations of ops stamps using recursion with early termination
    function<bool(int, int, vector<string>&)> solve = [&](int pos, int used, vector<string>& g) -> bool {
        if (used == ops) {
            return canReach(g);
        }
        if (pos >= numStamps || used + (numStamps - pos) < ops) {
            return false;
        }
        
        // Early termination: if already reachable, no need to try more stamps
        if (canReach(g)) return true;
        
        // Try not using this stamp
        if (solve(pos + 1, used, g)) return true;
        
        // Try using this stamp
        vector<string> newGrid = g;
        int a = stamps[pos].first;
        int b = stamps[pos].second;
        
        for (int i = a; i < a + N; i++) {
            for (int j = b; j < b + N; j++) {
                newGrid[i][j] = '.';
            }
        }
        
        if (solve(pos + 1, used + 1, newGrid)) return true;
        
        return false;
    };
    
    vector<string> currentGrid = grid;
    if (solve(0, 0, currentGrid)) {
        cout << ops << endl;
        return 0;
    }
}

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