史上最难C++题，不用python做不出
2025-07-28 20:42:24
发布于：浙江
141阅读
0回复
0点赞
话不多说直接上链接
mxcm岩浆跑酷
全部评论 3
豆包写出来了
#include <bits/stdc++.h>
using namespace std;struct Block {
int id;
vector<pair<int, int>> points;
bool is_start;
bool is_end;
};int main() {
int n, m;
cin >> n >> m;
vector<string> grid(m);
for (int i = 0; i < m; ++i) {
cin >> grid[i];
}
int x, a;
cin >> x >> a;int sx = -1, sy = -1, ex = -1, ey = -1; for (int y = 0; y < m; ++y) { for (int x = 0; x < n; ++x) { char c = grid[y][x]; if (c == 'S') { sx = x; sy = y; } else if (c == 'E') { ex = x; ey = y; } } } vector<vector<bool>> visited(m, vector<bool>(n, false)); vector<Block> blocks; vector<pair<int, int>> dirs = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}}; for (int y = 0; y < m; ++y) { for (int x = 0; x < n; ++x) { char c = grid[y][x]; if ((c == '#' || c == 'S' || c == 'E') && !visited[y][x]) { queue<pair<int, int>> q; q.push({x, y}); visited[y][x] = true; Block b; b.id = blocks.size(); b.is_start = false; b.is_end = false; while (!q.empty()) { auto [cx, cy] = q.front(); q.pop(); b.points.emplace_back(cx, cy); if (grid[cy][cx] == 'S') { b.is_start = true; } if (grid[cy][cx] == 'E') { b.is_end = true; } for (auto [dx, dy] : dirs) { int nx = cx + dx; int ny = cy + dy; if (nx >= 0 && nx < n && ny >= 0 && ny < m) {2025-08-07 来自 浙江
0再加一段
if (!visited[ny][nx] && (grid[ny][nx] == '#' || grid[ny][nx] == 'S' || grid[ny][nx] == 'E')) {
visited[ny][nx] = true;
q.emplace(nx, ny);
}
}
}
}
blocks.push_back(b);
}
}
}int start_id = -1, end_id = -1; for (int i = 0; i < blocks.size(); ++i) { if (blocks[i].is_start) { start_id = i; } if (blocks[i].is_end) { end_id = i; } } if (start_id == -1 || end_id == -1) { cout << -1 << endl; return 0; } if (start_id == end_id) { cout << 0 << endl; return 0; } int C = blocks.size(); const int INF = 1e9; vector<vector<int>> dist(C, vector<int>(C, INF)); for (int i = 0; i < C; ++i) { for (int j = i + 1; j < C; ++j) { int min_d = INF; for (auto [x1, y1] : blocks[i].points) { for (auto [x2, y2] : blocks[j].points) { int dx = abs(x1 - x2); int dy = abs(y1 - y2); min_d = min(min_d, max(dx, dy)); } } dist[i][j] = min_d; dist[j][i] = min_d; } } vector<vector<unordered_set<long long>>> visited_mask(C, vector<unordered_set<long long>>(a + 1)); queue<tuple<int, int, long long, int>> q; long long initial_mask = 1LL << start_id; q.emplace(start_id, a, initial_mask, 0); visited_mask[start_id][a].insert(initial_mask); int answer = -1; bool found = false; while (!q.empty()) { auto [u, a_rem, mask, steps] = q.front(); q.pop(); if (u == end_id) { answer = steps; found = true; break; } for (int v = 0; v < C; ++v) { if (v == u) continue;2025-08-07 来自 浙江
0再加一段
if (mask & (1LL << v)) continue;int d = dist[u][v]; if (d == INF || d < 1) continue; if (d <= x) { long long new_mask = mask | (1LL << v); if (!visited_mask[v][a_rem].count(new_mask)) { visited_mask[v][a_rem].insert(new_mask); q.emplace(v, a_rem, new_mask, steps + 1); } } if (a_rem >= 1 && d <= 2 * x) { int new_a = a_rem - 1; long long new_mask = mask | (1LL << v); if (!visited_mask[v][new_a].count(new_mask)) { visited_mask[v][new_a].insert(new_mask); q.emplace(v, new_a, new_mask, steps + 1); } } } } cout << (found ? answer : -1) << endl; return 0;}
2025-08-07 来自 浙江
0
有帮助，赞一个