제출 #1253852

#제출 시각아이디문제언어결과실행 시간메모리
1253852shawnchang51Maze (JOI23_ho_t3)C++17
0 / 100
2095 ms328 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...