hdu3442(BFS)

링크: 클릭 하여 링크 열기
제목: n * m 의 행렬 중 다섯 가지 방어 장비 가 있 습 니 다. 'A' 데 미 지 범 위 는 2 이 고 살상력 은 1 입 니 다. 'B '피해 범 위 는 3, 살상력 은 2;'C '그 칸 에 있 을 때 만 데 미 지 를 받 을 수 있 고 살상력 은 3 입 니 다.'D '데 미 지 범 위 는 2, 살상력 은 4;'E '데 미 지 범 위 는 1 이 고 살상력 은 5 입 니 다.' 와 'C' 만 갈 수 있 습 니 다. 특정한 방어 장비 의 공격 을 받 으 면 같은 장비 에 더 이상 공격 당 하지 않 습 니 다. '$' 를 기점 으로 '!'종점 을 위해 종점 까지 가 는 데 가장 작은 데 미 지 를 묻는다.
코드:

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m;
int xx[]={1,-1,0,0};
int yy[]={0,0,1,-1};
int sign[55][55][2][2][2][2][2];                //    2^5   
char str[55][105];
struct node{
    int x,y,sum,flag0,flag1,flag2,flag3,flag4;
    friend bool operatorb.sum;
    }
};
struct edge{
    int x,y;
};
vector A,B,D,E;
int judge0(int p,int q){
    int i;
    for(i=0;i qu;
    node cur,temp;
    qu.push(st);
    while(qu.size()){
        cur=qu.top(),qu.pop();
        if(cur.x==en.x&&cur.y==en.y)
        return cur.sum;
        for(i=0;i<4;i++){
            temp.x=cur.x+xx[i];
            temp.y=cur.y+yy[i];
            temp.sum=cur.sum;
            temp.flag0=cur.flag0,temp.flag1=cur.flag1,temp.flag2=cur.flag2,temp.flag3=cur.flag3,temp.flag4=cur.flag4;
            if(sign[temp.x][temp.y][cur.flag0][cur.flag1][cur.flag2][cur.flag3][cur.flag4])
            continue;
            if(temp.x>=1&&temp.x<=n&&temp.y>=1&&temp.y<=m){
            if(str[temp.x][temp.y]=='.'){       //  '.' 'C'  
            if(!cur.flag0&&judge0(temp.x,temp.y))
            temp.flag0=1,temp.sum+=1;
            if(!cur.flag1&&judge1(temp.x,temp.y))
            temp.flag1=1,temp.sum+=2;
            if(!cur.flag3&&judge3(temp.x,temp.y))
            temp.flag3=1,temp.sum+=4;
            if(!cur.flag4&&judge4(temp.x,temp.y))
            temp.flag4=1,temp.sum+=5;
            sign[temp.x][temp.y][temp.flag0][temp.flag1][temp.flag2][temp.flag3][temp.flag4]=1;
            qu.push(temp);
            }
            else if(str[temp.x][temp.y]=='C'){
            if(!cur.flag0&&judge0(temp.x,temp.y))
            temp.flag0=1,temp.sum+=1;
            if(!cur.flag1&&judge1(temp.x,temp.y))
            temp.flag1=1,temp.sum+=2;
            if(!cur.flag2)
            temp.flag2=1,temp.sum+=3;
            if(!cur.flag3&&judge3(temp.x,temp.y))
            temp.flag3=1,temp.sum+=4;
            if(!cur.flag4&&judge4(temp.x,temp.y))
            temp.flag4=1,temp.sum+=5;
            sign[temp.x][temp.y][temp.flag0][temp.flag1][temp.flag2][temp.flag3][temp.flag4]=1;
            qu.push(temp);
            }
            }
        }
    }
    return -1;
}
int main(){
    int i,j,t,ans,cas;
    node st,en;
    scanf("%d",&t);
    for(cas=1;cas<=t;cas++){
        A.clear(),B.clear();
        D.clear(),E.clear();
        memset(sign,0,sizeof(sign));
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                cin>>str[i][j];
                if(str[i][j]=='$'){
                st.x=i,st.y=j,st.sum=0;
                st.flag0=st.flag1=st.flag2=st.flag3=st.flag4=0;
                }
                if(str[i][j]=='!'){
                en.x=i,en.y=j,en.sum=0;
                str[i][j]='.';
                }
                if(str[i][j]=='A')              //            
                A.push_back((edge){i,j});
                if(str[i][j]=='B')
                B.push_back((edge){i,j});
                if(str[i][j]=='D')
                D.push_back((edge){i,j});
                if(str[i][j]=='E')
                E.push_back((edge){i,j});
            }
        }
        ans=bfs(st,en);
        printf("Case %d: %d
",cas,ans);
    }
    return 0;
}