hdu1044(bfs+dfs/bfs+状态压缩)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1044
题目大意：
在一个迷宫中，从起点走到终点，还有几个宝物，问在给定的时间内，到达终点后所能获取的最大价值。

1.状态压缩记录状态，用十位的二进制数表示每个宝石选还是不选，共有2^10=1024个状态,开个数组vis[maxn][maxn][1024]判断在每一点是否达到该状态，bfs搜索最短路径，W*H*1024个状态都要搜到，复杂度较高

#include <stdio.h>
#include <queue>
#include <memory.h>
using namespace std;
int W, H, L, M;
bool vis[55][55][1100];
char g[55][55];
int money[15];

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

struct node
{
    int x, y, state, val, time;
};

bool check(int x, int y){
    if (x<0 || x>H - 1 || y<0 || y>W - 1)return false;
    if (g[x][y] == '*')return false;
    return true;
}



int bfs(int sx, int sy)
{
    memset(vis, 0, sizeof(vis));
    queue<node>q;
    node cur, next;
    cur.x = sx;
    cur.y = sy;
    cur.state = 0;
    cur.time = 0;
    cur.val = 0;
    q.push(cur);
    vis[sx][sy][0] = 1;
    int ans = -1;
    while (!q.empty()){
        cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i){
            next.x = cur.x + dx[i];
            next.y = cur.y + dy[i];
            if (check(next.x, next.y)){
                if (g[next.x][next.y] >= 'A'&&g[next.x][next.y] <= 'J'){
                    int tmp = g[next.x][next.y] - 'A';
                    if (!(cur.state&(1<<tmp))){//这一句WA到死，不仅要判断状态是否到达过，而且每个宝石只能拿一次啊，101和100不是同一个状态，但拿了同一个宝石
                        next.state = cur.state | (1 << tmp);
                        next.val = cur.val + money[tmp];
                    }
                }
                else{
                    next.state = cur.state;
                    next.val = cur.val;
                }
                if (!vis[next.x][next.y][next.state]){
                    next.time = cur.time + 1;
                    vis[next.x][next.y][next.state] = 1;
                    if (g[next.x][next.y] == '<'){
                        ans = max(ans, next.val);
                    }
                    if (next.time == L)continue;
                    q.push(next);                
                }
            }
            
            
        }
    }
    return ans;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    int T, sx, sy;
    scanf("%d", &T);
    for (int _case = 1; _case <= T; ++_case){
        scanf("%d %d %d %d", &W, &H, &L, &M);
        for (int i = 0; i < M; ++i)scanf("%d", &money[i]);
        for (int i = 0; i < H; ++i)
        {
            scanf("%s", g[i]);
            for (int j = 0; j < W; ++j)
            {
                if (g[i][j] == '@')
                {
                    sx = i;
                    sy = j;
                    g[i][j] == '.';
                }
            }
        }
        printf("Case %d:\n", _case);
        int ans = bfs(sx, sy);
        if (ans >= 0)printf("The best score is %d.\n", ans);
        else printf("Impossible\n");
        if (_case < T)printf("\n");
    }
    return 0;
}

2.bfs+dfs

bfs找到出口到每个宝石，每个宝石之间和所有宝石到出口的路径，只用搜索每个x,y是否已经到达过，复杂度大大降低

dfs找到在time limit内是否能找到出口，记录能拿到的宝石的最大值

注意dfs的剪枝，如果此时拿到宝石的数量已经达到总量，可以不用继续搜索下去了

#include<stdio.h>
#include<memory.h>
#include<queue>

using namespace std;

char g[55][55];
int dis[30][30];
int j[15]; int tot;
bool vis1[55][55];
bool vis2[30];
int step[55][55];
int t, w, h, L, m;

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

bool check(int x, int y)
{
    if (vis1[x][y])return false;
    if (x < 0 || x>h - 1 || y<0 || y>w - 1)return false;
    if (g[x][y] == '*')return false;
    return true;
}

void bfs(int x, int y, int tag)
{
    memset(vis1, 0, sizeof(vis1));
    memset(step, 0, sizeof(step));
    queue<int>q;
    q.push(x*w + y);
    vis1[x][y] = 1;
    step[x][y] = 0;
    while (!q.empty()){
        int cur = q.front();
        q.pop();
        int x = cur / w; 
        int y = cur%w;
        for (int i = 0; i < 4; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (check(nx, ny)){
                vis1[nx][ny] = 1;
                step[nx][ny] = step[x][y] + 1;
                if (g[nx][ny] == '@')dis[tag][0] = step[nx][ny];
                else if (g[nx][ny] == '<')dis[tag][m + 1] = step[nx][ny];
                else if ('A' <= g[nx][ny] && g[nx][ny] <= 'J') dis[tag][g[nx][ny] - 'A' + 1] = step[nx][ny];
                q.push(nx*w+ny);
            }
        }
    }
}

int ans;

void dfs(int tag,int val,int t)
{
    if (t > L)return;
    if (ans == tot)return;
    if (tag > m&&val > ans){
        ans = val;
        return;
    }

    for (int i = 0; i <= m + 1; ++i){
        if (!vis2[i] && dis[tag][i]){
            vis2[i] = 1;
            dfs(i, val + j[i], t + dis[tag][i]);
            vis2[i] = 0;
        }
    }
}

int main()
{
    //freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    for (int c = 1; c <= t; ++c){
        memset(dis, 0, sizeof(dis));
        tot = 0;
        scanf("%d %d %d %d", &w, &h, &L, &m);
        for (int i = 1; i <= m; ++i){
            scanf("%d", &j[i]);
            tot += j[i];
        }
        j[0] = 0; j[m + 1] = 0;//0代表入口，m+1代表出口，1~m代表宝石
        for (int i = 0; i < h; ++i){
            scanf("%s", g[i]);
        }
        
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                if (g[i][j] == '@')bfs(i, j, 0);
                else if (g[i][j] == '<')bfs(i, j, m + 1);
                else if ('A' <= g[i][j] && g[i][j] <= 'J')bfs(i, j, g[i][j] - 'A' + 1);
            }
        }
        ans = -1;
        memset(vis2, 0, sizeof(vis2));
        vis2[0] = 1;
        dfs(0,0,0);
        printf("Case %d:\n", c);
        if (ans >= 0)printf("The best score is %d.\n", ans);
        else printf("Impossible\n");
        if (c <t)printf("\n");
    }
    return 0;
}