< 8; i++) {cin >> c;ed += c;}int ans = bfs();string path;for (auto p = pre[ed]; p.first != "-1"; p = pre[p.first]) path += p.second;reverse(path.begin(), path.end());cout << ans << endl;if (path != "") cout << path << endl;return 0;}
3. 1106. 山峰和山谷
void bfs(int x, int y) {int num = g[x][y];que.push({ x, y });vis[x][y] = true;bool is_peak = true, is_valley = true;while (que.size()) {auto p = que.front(); que.pop();int x = p.first, y = p.second;for (int dx = -1; dx <= 1; dx++) {for (int dy = -1; dy <= 1; dy++) {int nx = x + dx, ny = y + dy;if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;if (g[nx][ny] > num) is_peak = false;else if (g[nx][ny] < num) is_valley = false;else if(!vis[nx][ny]){vis[nx][ny] = true;que.push({ nx, ny });}}}}if (is_peak) peak++;if (is_valley) valley++;}void solve() {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (!vis[i][j]) bfs(i, j);}}printf("%d %d\n", peak, valley);}
4. 1098. 城堡问题
int N, M;int g[maxn][maxn];bool vis[maxn][maxn];typedef pair P;queue que;int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};int bfs(int x, int y) {int cnt = 0;que.push({ x, y });vis[x][y] = true;while (que.size()) {auto p = que.front(); que.pop();cnt++;int x = p.first, y = p.second;for (int i = 0; i < 4; i++) {if (g[x][y] >> i & 1) continue;int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M || vis[nx][ny]) continue;vis[nx][ny] = true;que.push({ nx, ny });}}return cnt;}void solve() {int cnt = 0, max_size = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (!vis[i][j]) {max_size = max(max_size, bfs(i, j));cnt++;}}}printf("%d\n%d\n", cnt, max_size);}
5. 179. 八数码
#include#include#include#include#include#includeusing namespace std;typedef pair P;int f(string s) {int res = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == 'x') continue;int num = s[i] - '1';int sx = num / 3, sy = num % 3, tx = i / 3, ty = i % 3;res += abs(sx - tx) + abs(sy - ty);}return res;}string bfs(string start) {char op[10] = "udlr";string end = "12345678x";int dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };priority_queue, greater> que;unordered_map, int> d;unordered_map, pair> pre;que.push(P(f(start), start));d[start] = 0;while (que.size()) {auto p = que.top(); que.pop();string state = p.second; int dis = p.first;if (state == end) break;int id = state.find('x');int x = id / 3, y = id % 3;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;string t = state;swap(t[nx * 3 + ny], t[x * 3 + y]);if (!d.count(t) || d[t] > d[state] + 1) {d[t] = d[state] + 1;que.push(P(f(t) + d[t], t));pre[t] = make_pair(op[i], state);}}}string path, now = end;while (now != start) {path += pre[now].first;now = pre[now].second;}reverse(path.begin(), path.end());return path;}int main() {char c;string start, nums;for (int i = 0; i < 9; i++) {cin >> c;start += c;if (c != 'x') nums += c;}int cnt = 0;for (int i = 0; i < 8; i++) {for (int j = 0; j < i; j++) {if (nums[j] > nums[i]) cnt++;}}if (cnt & 1) cout << "unsolvable\n";else cout << bfs(start) << endl;return 0;}
三、图论 1.1126. 最小花费
double bfs() {d[A] = 1;priority_queue que;que.push({ 1, A });while (que.size()) {auto p = que.top(); que.pop();int u = p.second; double dist = p.first;if (vis[u]) continue;vis[u] = true;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] < d[u] * w[i]) {d[v] = d[u] * w[i];que.push({ d[v], v });}}}return 100.0 / d[B];}
8cbad024595760f93e7fc991cebb647a
2.340. 通信线路
#include#include#include#includeusing namespace std;const int maxn = 1010, maxm = 200010, INF = 1e9;int h[maxn], e[maxm], ne[maxm], idx, w[maxm], N, M, K, d[maxn];bool vis[maxn];void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;}bool bfs(int x) {memset(vis, false, sizeof vis);fill(d, d + maxn, INF);d[1] = 0;deque