[BFS]HDU1044 Collect More Jewels

HDU1044 Collect More Jewels两遍BFS，首先需要记录一下每个点到DEST的距离，，然后就可以搜了。当然也可以直接A*搞一下，估值函数设为f(x)={dis<代码:;const int MAX = 51;int W, H, L, M;int fetch[MAX];char str[MAX][MAX];bool vis[MAX][MAX][1 << 11];int dis[MAX][MAX];struct node {int x, y;int value;int vis;int money;} S, T;int d[4][2] = {-1,0, 0,1, 1,0, 0,-1};inline bool valid(int x, int y) {return x >= 0 && y >= 0 && x < H && y < W && str[x][y] != ‘*’;}void BFS1(const node& S) {queue<node> Q;node p, q;Q.push(S);memset(dis, -1, sizeof(dis));dis[S.x][S.y] = 0;while (!Q.empty()) {p = Q.front();Q.pop();q.value = p.value + 1;for (int i = 0; i < 4; ++i) {q.x = p.x + d[i][0];q.y = p.y + d[i][1];if (valid(q.x, q.y) && dis[q.x][q.y] == -1) {dis[q.x][q.y] = q.value;Q.push(q);}}}}int BFS2(const node& S, const node& T) {memset(vis, false, sizeof(vis));vis[S.x][S.y][S.vis] = true;queue<node> Q;node p, q;Q.push(S);int ans = -1;while (!Q.empty()) {p = Q.front();//printf(“fetch(%d,%d)\n”, p.x, p.y);Q.pop();q.value = p.value + 1;for (int i = 0; i < 4; ++i) {q.x = p.x + d[i][0];q.y = p.y + d[i][1];if (valid(q.x, q.y)) {//printf(“1:(%d,%d)\n”, q.x, q.y);if (q.value + dis[q.x][q.y] <= L) {//printf(“2:(%d,%d)\n”, q.x, q.y);if (isalpha(str[q.x][q.y])) {int tp = 1 << (str[q.x][q.y] – ‘A’);q.vis = p.vis | tp;q.money = p.money + ((p.vis & tp) ? 0 : fetch[str[q.x][q.y] – ‘A’]);} else {q.vis = p.vis;q.money = p.money;}if (!vis[q.x][q.y][q.vis]) {//printf(“3:(%d,%d)\n”, q.x, q.y);vis[q.x][q.y][q.vis] = true;//printf(“vis(%d, %d, %d, %d)\n”, q.x, q.y, q.vis, q.money);Q.push(q);if (q.x == T.x && q.y == T.y) {ans = max(ans, q.money);}}}}}}return ans;}int main() {int cas;scanf(” %d”, &cas);for (int t = 1; t <= cas; ++t) {scanf(” %d %d %d %d”, &W, &H, &L, &M);for (int i = 0; i < M; ++i) {scanf(” %d”, fetch + i);}for (int i = 0; i < H; ++i) {scanf(” %s”, str[i]);for (int j = 0; j < W; ++j) {if (str[i][j] == ‘@’) {S.x = i;S.y = j;S.value = S.vis = S.money = 0;str[i][j] = ‘.’;} else if (str[i][j] == ‘<‘) {T.x = i;T.y = j;T.value = 0;str[i][j] = ‘.’;}}}BFS1(T);int ans = BFS2(S, T);if (t > 1) puts(“”);printf(“Case %d:\n”, t);if (ans < 0) {puts(“Impossible”);} else {printf(“The best score is %d.\n”, ans);}}return 0;}数学公式

使用MathJax渲染LaTex 数学公式，详见math.stackexchange.com.

行内公式，数学公式为：。块级公式：

今天的长相厮守，只是尽力而为而已。