HDU1429胜利大逃亡(续)&&HDU 1885 Key Task BFS+状态压缩+水-白红宇

HDU1429胜利大逃亡(续)&&HDU 1885 Key Task BFS+状态压缩+水

阅读量：4309 次

发布时间：2019-06-06

本文共 2888 字，大约阅读时间需要 9 分钟。

HDU1429

只有10把钥匙 1<<10足够了

标记用三维数组

用Linux好不习惯继续克服～

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define MAXN 11111#include
              
               const int INF = 999999;char mp[33][33];bool vis[33][33][1026];int n,m;struct node{ int x,y,step; int key;};queue
               
                q;int xx[4]= {1,0,-1,0};int yy[4]= {0,1,0,-1};int bfs(int x,int y){ while(!q.empty()) q.pop(); memset(vis,false,sizeof(vis)); node front,rear; front.x=x,front.y=y; front.key=0; front.step=0; vis[x][y][0]=true; q.push(front); while(!q.empty()) { front=q.front(); q.pop(); for(int i=0; i<4; i++) { int dx=front.x+xx[i],dy=front.y+yy[i]; if(dx>=0&&dy>=0&&dx
                
                 
                  ='a'&&mp[dx][dy]<='z')//拿到钥匙 { vis[dx][dy][front.key]=true;//标记 rear.key =(front.key )| ( 1<<(mp[dx][dy]-'a'));//添加钥匙 rear.x=dx,rear.y=dy,rear.step=front.step+1; q.push(rear); } else if(mp[dx][dy]>='A'&&mp[dx][dy]<='Z')//遇到门 { if(front.key&(1<<(mp[dx][dy]-'A')))//如果有对应的钥匙 { rear.x=dx,rear.y=dy,rear.key=front.key,rear.step=front.step+1; vis[dx][dy][rear.key]=true; q.push(rear); } } else { rear.x=dx,rear.y=dy,rear.key=front.key,rear.step=front.step+1; vis[dx][dy][rear.key]=true; q.push(rear); } } } } return 0;}int main(){ int t; // freopen("in.txt","r",stdin); while(scanf("%d%d%d",&n,&m,&t)!=EOF) { node s; for(int i=0; i
                  
                   =t) printf("-1\n"); else printf("%d\n",ans); } return 0;}

HDU1885

这个就4把钥匙

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define MAXN 11111#include
              
               const int INF = 999999;char mp[133][133];bool vis[133][133][33];int n,m;int ke[28];struct node{ int x,y,step; int key;};queue
               
                q;int xx[4]= {1,0,-1,0};int yy[4]= {0,1,0,-1};int bfs(int x,int y){ while(!q.empty()) q.pop(); memset(vis,false,sizeof(vis)); node front,rear; front.x=x,front.y=y; front.key=0; front.step=0; vis[x][y][0]=true; q.push(front); while(!q.empty()) { front=q.front(); q.pop(); for(int i=0; i<4; i++) { int dx=front.x+xx[i],dy=front.y+yy[i]; if(dx>=0&&dy>=0&&dx
                
                 
                  ='a'&&mp[dx][dy]<='z')//拿钥匙 { vis[dx][dy][front.key]=true; rear.key =(front.key )| ( 1<<(ke[mp[dx][dy]-'a'])); rear.x=dx,rear.y=dy,rear.step=front.step+1; q.push(rear); } else if(mp[dx][dy]>='A'&&mp[dx][dy]<='Z')//开门 { if(front.key&(1<<(ke[mp[dx][dy]-'A']))) { rear.x=dx,rear.y=dy,rear.key=front.key,rear.step=front.step+1; vis[dx][dy][rear.key]=true; q.push(rear); } } else { rear.x=dx,rear.y=dy,rear.key=front.key,rear.step=front.step+1; vis[dx][dy][rear.key]=true; q.push(rear); } } } } return 0;}int main(){ //freopen("in.txt","r",stdin); ke['a'-'a']=0,ke['b'-'a']=1,ke['r'-'a']=2,ke['g'-'a']=3; while(scanf("%d%d",&n,&m),n+m) { node s; for(int i=0; i