hdu 2416 (검색)

제목: 그림 을 보 여 줍 니 다. $는 보물 의 위치 입 니 다. 그림 의 경계 에 입구 가 있 습 니 다. \ # 폭약 이 없 는 것 을 의미 합 니 다. A - Z 는 폭약 의 수량 을 대표 합 니 다. 한 입구 에서 만 들 어 갈 수 있 습 니 다. 그림 에는 돌 을 대표 하 는 숫자 가 있 습 니 다. 폭약 하 나 를 소모 하여 돌 을 폭파 하 는 데 시간 이 걸 리 지 않 으 면 해당 하 는 시간 이 소 모 됩 니 다. 적어도 보물 장소 에 도착 하 는 시간 이 얼마 인지 물 어보 세 요.
사고: 처음에 직접 검색 하려 고 했 는데 잠깐 쓰 면 안 된다 고 생각 했 어 요. 만약 에 몇 가지 경로 에 도착 하 는 시간 이 같 으 면 우 리 는 폭약 을 가장 많이 휴대 해 야 해 요. 그러면 뒤의 시간 이 가장 적 게 보장 할 수 있어 요.그래서 그림 을 3 차원 지도 로 늘 려 점 마다 지 니 고 있 는 폭약 의 최 단 시간 을 기록 했다.

#include<iostream>
#include<queue>
using namespace std;
const int N=110;
const int inf=0x3fffffff;
int dir[4][2]={0,1,0,-1,1,0,-1,0},n,m,t[N][N][27];
bool vis[N][N][27];
char map[N][N];
struct node
{
    int x,y,k;
}cur,next;
bool judge(int x,int y)
{
    if(x<0||x>=n||y<0||y>=m||map[x][y]=='*')return false;
    return true;
}
void bfs()
{
    int i,j,x,y,ii,k,sx,sy,ans=inf;
    queue<node>Q;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            for(ii=0;ii<27;ii++)
            t[i][j][ii]=inf,vis[i][j][ii]=false;
            if(map[i][j]=='$') sx=i,sy=j;              
            else if(map[i][j]=='#'||map[i][j]>='A'&&map[i][j]<='Z')
            {
                cur.x=i;cur.y=j;
                if(map[i][j]=='#')cur.k=0;
                else cur.k=map[i][j]-'A'+1;
                Q.push(cur);
                map[i][j]='*';t[i][j][cur.k]=0;vis[i][j][cur.k]=true;
            }
        }
    }
    while(!Q.empty())
    {
        cur=Q.front();Q.pop();   
        vis[cur.x][cur.y][cur.k]=false;
        for(i=0;i<4;i++)
        {
            next.x=x=cur.x+dir[i][0];
            next.y=y=cur.y+dir[i][1];
            next.k=k=cur.k;
            if(!judge(x,y))continue;
            if((map[x][y]=='.'||map[x][y]=='$')&&t[x][y][k]>t[cur.x][cur.y][k])//    
            {
                t[x][y][k]=t[cur.x][cur.y][k];
                if(!vis[x][y][k]){Q.push(next);vis[x][y][k]=true;}
            }
            else if(map[x][y]>='1'&&map[x][y]<='9')
            {
                int temp=map[x][y]-'0';
                if(t[x][y][k]>t[cur.x][cur.y][k]+temp)//  
                {
                    t[x][y][k]=t[cur.x][cur.y][k]+temp;
                    if(!vis[x][y][k]){Q.push(next);vis[x][y][k]=true;}
                }
                if(k>0&&t[x][y][k-1]>t[cur.x][cur.y][k])// 
                {
                    next.k--;
                    t[x][y][k-1]=t[cur.x][cur.y][k];
                    if(!vis[x][y][k-1]){Q.push(next);vis[x][y][k-1]=true;}
                }
            }
        }
    }
    for(i=0;i<27;i++)
        if(ans>t[sx][sy][i]){ans=t[sx][sy][i];}
    if(ans<inf)printf("%d
",ans);
    else printf("IMPOSSIBLE
");
}
int main()
{
    n=0;
    while(gets(map[n]),map[n][0]!='-')
    {
        if(map[n][0]=='\0')
        {
            m=strlen(map[0]);
            bfs();n=-1;           
        }
        n++;
    }
    return 0;
}