hdu5025 状态压缩搜索 《网络赛题》

2014年网络赛题

先说下题意 告诉你起点 终点 n*n的地图 地图是由空 满 有一个标号的钥匙 蛇组成 问能不能到达终点

你只有拿到n一下的所有钥匙才能拿到n这把钥匙 （比如现在要拿表号位5的钥匙 你必须有1 2 3 4的钥匙 如果没有 但也能走这个格子） 但能走所有非满的格子 蛇只能杀一次

#include
  
   
#include
   
     #include
    
      #include
      
      using namespace std
      ; struct node
       { int x
      ,y
      ,step
      ,key
      ; int kill
      ; }a
      ,b
      ; int mark
      [110
      ][110
      ][10
      ][50
      ],n
      ,m
      ,Min
      ,flash
      ;//mark记录状态 char map
      [110
      ][110
      ]; int dir
      [4
      ][2
      ]={0
      ,1
      ,0
      ,-1
      ,1
      ,0
      ,-1
      ,0
      }; int bfs
      (int starx
      ,int stary
      ) { a
      .x
      =starx
      ; a
      .y
      =stary
      ; a
      .step
      =0
      ; a
      .key
      =0
      ; a
      .kill
      =0
      ; memset
      (mark
      ,127
      ,sizeof(mark
      )); mark
      [a
      .x
      ][a
      .y
      ][a
      .key
      ][a
      .kill
      ]=0
      ; queue
      <node
      >q
      ; q
      .push
      (a
      ); while(!q
      .empty
      ()) { b
      =q
      .front
      (); q
      .pop
      (); if(map
      [b
      .x
      ][b
      .y
      ]=='T'
      &&b
      .key
      ==m
      ) { if(b
      .step
      <Min
      ) Min
      =b
      .step
      ; flash
      =1
      ; continue; } for(int i
      =0
      ;i
      <4
      ;i
      ++) { a
      .x
      =b
      .x
      +dir
      [i
      ][0
      ]; a
      .y
      =b
      .y
      +dir
      [i
      ][1
      ]; a
      .step
      =b
      .step
      +1
      ; a
      .key
      =b
      .key
      ; a
      .kill
      =b
      .kill
      ; if(a
      .x
      <0
      ||a
      .x
      >=n
      ||a
      .y
      <0
      ||a
      .y
      >=n
      ) continue; if(map
      [a
      .x
      ][a
      .y
      ]=='#'
      ) continue; /*if(mark[a.x][a.y][a.key][a.kill]) continue; { if(a.step>mark[a.x][a.y][a.key][a.kill]) continue; }*/
       if(map
      [a
      .x
      ][a
      .y
      ]>='a'
      &&map
      [a
      .x
      ][a
      .y
      ]<='z'
      ) { int t
      =map
      [a
      .x
      ][a
      .y
      ]-'a'
      ; if((a
      .kill
      &(1
      <<t
      ))==0
      ) { a
      .kill
      =a
      .kill
      |(1
      <<t
      ); a
      .step
      ++; } //mark[a.x][a.y][a.key][a.kill]=a.step; //q.push(a); 
       } else if(map
      [a
      .x
      ][a
      .y
      ]>='1'
      &&map
      [a
      .x
      ][a
      .y
      ]<='9'
      ) { int x
      =map
      [a
      .x
      ][a
      .y
      ]-'0'
      ; if(a
      .key
      ==x
      -1
      ) a
      .key
      =x
      ; //mark[a.x][a.y][a.key][a.kill]=a.step; //if(a.step<=mark[a.x][a.y][a.key][a.kill]) q.push(a); 
       } else { //mark[a.x][a.y][a.key][a.kill]=a.step; //q.push(a); 
       } if(a
      .step
      <mark
      [a
      .x
      ][a
      .y
      ][a
      .key
      ][a
      .kill
      ]) { mark
      [a
      .x
      ][a
      .y
      ][a
      .key
      ][a
      .kill
      ]=a
      .step
      ; q
      .push
      (a
      ); } } } return 0
      ; } int main() { int i
      ,j
      ; while(~scanf
      ("%d%d"
      ,&n
      ,&m
      ),n
      +m
      ) { for(i
      =0
      ;i
      <n
      ;i
      ++) scanf
      ("%s"
      ,map
      [i
      ]); char t
      ='a'
      ; int starx
      ,stary
      ,endx
      ,endy
      ; for(i
      =0
      ;i
      <n
      ;i
      ++) { for(j
      =0
      ;j
      <n
      ;j
      ++) { if(map
      [i
      ][j
      ]=='K'
      ) { starx
      =i
      ; stary
      =j
      ; } else if(map
      [i
      ][j
      ]=='S'
      ) { map
      [i
      ][j
      ]=t
      ++; } else if(map
      [i
      ][j
      ]=='T'
      ) { endx
      =i
      ; endy
      =j
      ; } } } Min
      =999999
      ; flash
      =0
      ; bfs
      (starx
      ,stary
      ); if(!flash
      ) printf
      ("impossible\n"
      ); else printf
      ("%d\n"
      ,Min
      ); } return 0
      ; }