HDU 2416 Treasure of the Chimp Island

状态搜索，一开始通过所有的入口开始bfs，超时了。其实可以通过加状态的方法来减少搜索的复杂度。即通过Time[x][y][dn]，表示走到x,y坐标，当前携带炸弹为dn的步数的最小值。把所有出口入队，然后广搜。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;

const int maxn = 110;
const int INF = 0x3f3f3f3f;

char map[maxn][maxn];
int Time[maxn][maxn][27];

int n, m;

vector<pair<int, int> > pos;

int bx, by;
int ex, ey;

struct node
{
    int x, y;
    int step, dn;
};

int check(int x, int y)
{
    if(x >= 0 && x < n && y >= 0 && y < m && map[x][y] != '*') return 1;
    return 0;
}

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

void bfs(int &ans)
{
    queue<node> Q;
    
    node cur, next;
    
    for(int i = 0; i < pos.size(); i++)
    {
        cur.x = pos[i].first/m, cur.y = pos[i].first%m;
        cur.step = 0, cur.dn = pos[i].second;
        Q.push(cur);
    }
    
    while(!Q.empty())
    {
        cur = Q.front(); Q.pop();
        int x = cur.x, y = cur.y, step = cur.step, dn = cur.dn;
        for(int i = 0; i < 4; i++)
        {
            next = cur;
            int newx = x+dx[i], newy = y+dy[i];
            if(!check(newx, newy)) continue;

            if((map[newx][newy] == '.' && Time[newx][newy][dn] > step))
            {
                next.x = newx, next.y = newy;
                next.step = step, next.dn = dn;
                Time[newx][newy][dn] = step;
                Q.push(next);
            }
            else if(isdigit(map[newx][newy]))
            {
                if((Time[newx][newy][dn] > step+map[newx][newy]-'0'))
                {
                    next.x = newx, next.y = newy;
                    next.step = step+map[newx][newy]-'0', next.dn = dn;
                    Time[newx][newy][dn] = step+map[newx][newy]-'0';
                    Q.push(next);    
                }
                if((dn >= 1 && Time[newx][newy][dn-1] > step))
                {
                    next.x = newx, next.y = newy;
                    next.step = step, next.dn = dn-1;
                    Time[newx][newy][dn-1] = step;
                    Q.push(next);
                }
            }
            else if(map[newx][newy] == '$' && step < ans)
                ans = step;
        }
    }
}

void init()
{
    pos.clear();
}

void build()
{
    memset(Time, INF, sizeof(Time));
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(map[i][j] == '$') ex = i, ey = j;
            if(isalpha(map[i][j]) || map[i][j] == '#')
            {
                int t;
                if(map[i][j] == '#') t = 0;
                else t = map[i][j]-'A'+1;
                pos.push_back(make_pair(i*m+j, t));
                map[i][j] = '*';
                Time[i][j][t] = 0;
            }
        }
    }
}

void rebuild()
{
    int ans = INF;
    bfs(ans);
    if(ans == INF) { printf("IMPOSSIBLE
"); }
    else printf("%d
", ans);
}

int main()
{
    for(;;)
    {
        init();
        n = 0;
        scanf("%s%*c", map[n]);
        if(strcmp(map[n], "--") == 0) break;
        n++;
        
        while(gets(map[n]))
        {
            if(strlen(map[n]) == 0) break;
            n++;
        }
        
        m = strlen(map[n-1]);
        
        build();
        rebuild();
    }
    return 0;
}