題目

$題目傳送門$

輸入輸出樣例
輸入樣例一

4 4 .... .S1. .... .... 10

輸出樣例一

2

輸入樣例二

7 7 ....... .1###2. .#...#. .#.B.#. .3...4. ..##... ......S 100 100 100 100

輸出樣例二

364

輸入樣例三

7 8 ........ ........ ....1B.. .S...... ....2... 3....... ........ 100 -100 100

輸出樣例三

0

輸入樣例四

1 1 S

輸出樣例四

0

題解

• 設$sum[i]$表示獲得寶藏的狀態為$i$時所得到的價值
• 設$f[i][j][k]$表示走到點$(i，j)$選取寶藏的狀態為$k$時的最小步數
• 答案為$sum[k]?f[s][t][k]$
• $DP$時$BFS$即可

$code$

#include <bits/stdc++.h> using namespace std; const int maxn = 25; const int maxm = 500; const int maxk = 1<<9; const int inf = 1e6 + 100; const int dx[4] = { 1, -1, 0, 0 }; const int dy[4] = { 0, 0, 1, -1 }; template <typename T> inline void read(T &s) { s = 0; T w = 1, ch = getchar(); while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); } while (isdigit(ch)) { s = (s<<1) + (s<<3) + (ch^48); ch = getchar(); } s *= w; } int n, m, s, t; int cnt, res; int val[maxm], sum[maxk]; int f[maxn][maxn][maxk]; char c[maxn][maxn]; struct node { int x, y, v; }; struct point { int x, y; } p[maxm]; inline bool check(int x, int y, int xx, int yy, int i) {if (xx == p[i].x && yy < p[i].y && x < xx) return true; if (x == p[i].x && y < p[i].y && x > xx) return true; return false; }void bfs() {res = 0; memset(f, -1, sizeof(f)); queue<node> q; q.push((node){s, t, 0}); f[s][t][0] = 0; while (!q.empty()) {node now = q.front(); q.pop(); int x = now.x, y = now.y, v = now.v; if (x == s && y == t) {res = max(res, sum[v] - f[x][y][v]); }for (int i = 0; i < 4; ++i) {int xx = x + dx[i], yy = y + dy[i], vv = v; if (xx < 1 || xx > n || yy < 1 || yy > m) continue; if (c[xx][yy] != 'S' && c[xx][yy] != '.') continue; for (int j = 1; j <= cnt; ++j) {if (check(x, y, xx, yy, j)) vv ^= 1<<(j-1); // cout << vv << endl; }if (f[xx][yy][vv] == -1) {f[xx][yy][vv] = f[x][y][v] + 1; q.push((node){xx, yy, vv}); }}} }int main() { // freopen("1.in", "r", stdin); read(n), read(m); for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> c[i][j]; if (c[i][j] == 'S') {s = i; t = j; } else if (c[i][j] != '.' && c[i][j] != '#' && c[i][j] != 'B') {p[c[i][j] - '0'].x = i; p[c[i][j] - '0'].y = j; ++cnt; }}}for (int i = 1; i <= cnt; ++i) read(val[i]); for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (c[i][j] == 'B') { p[++cnt].x = i; p[cnt].y = j; val[cnt] = -inf; }}}for (int i = 1; i < (1<<cnt); ++i) {for (int j = 1; j <= cnt; ++j) {if (i & (1<<(j-1))) sum[i] += val[j]; }}bfs();printf("%d\n", res);return 0; }

總結

以上是生活随笔為你收集整理的CF375C Circling Round Treasures（BFS+DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。