拯救大兵瑞恩 http://acm.hdu.edu.cn/showproblem.php?pid=4845

 1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int M=16; 7 int mp[M][M][M][M]; 8 int key[M][M]; 9 bool vis[M][M][1<<11];10 int n,m;11 struct Q{12     int x,y,step,mykey;13 }now,pre;14 queue<Q> q;15 int dx[]={0,0,1,-1};16 int dy[]={1,-1,0,0};17 int bfs(){18     now.x=1;19     now.y=1;20     now.step=0;21     now.mykey=key[1][1];22     mt(vis,0);23     vis[1][1][now.mykey]=true;24     while(!q.empty()) q.pop();25     q.push(now);26     while(!q.empty()){27         pre=q.front();28         q.pop();29         if(pre.x==n&&pre.y==m) return pre.step;30         for(int i=0;i<4;i++){31             int tx=pre.x+dx[i];32             int ty=pre.y+dy[i];33             if(tx>=1&&tx<=n&&ty>=1&&ty<=m){34                 int need=mp[pre.x][pre.y][tx][ty];35                 if(need==-1||((pre.mykey>>need)&1)){36                     now.x=tx;37                     now.y=ty;38                     now.step=pre.step+1;39                     now.mykey=pre.mykey|key[tx][ty];40                     if(!vis[tx][ty][now.mykey]){41                         vis[tx][ty][now.mykey]=true;42                         q.push(now);43                     }44                 }45             }46         }47     }48     return -1;49 }50 int main(){51     int p,x1,y1,x2,y2,op;;52     while(~scanf("%d%d%d",&n,&m,&p)){53         scanf("%d",&p);54         mt(mp,-1);55         while(p--){56             scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&op);57             mp[x1][y1][x2][y2]=op;58             mp[x2][y2][x1][y1]=op;59         }60         scanf("%d",&p);61         mt(key,0);62         while(p--){63             scanf("%d%d%d",&x1,&y1,&op);64             key[x1][y1]|=(1<<op);65         }66         printf("%d\n",bfs());67     }68     return 0;69 }