1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5  6 int n , m; 7 const int size = 55; 8 int wall[size][size][size][size]; 9 int dir[4][2] = {1,0,-1,0,0,1,0,-1};10 int key[size][size];11 bool vis[size][size][1<<12];12 struct node13 {14     int x , y , key , T; 15     node(){};16     node( int u , int v , int w , int p ):x(u),y(v),key(w),T(p){};    17 };18 queue<node> q;19 20 void init( )21 {22     memset( vis , false , sizeof(vis) );23     memset( wall , -1 , sizeof(wall) );24     memset( key , 0 , sizeof(key) );25     while( !q.empty() )26         q.pop();    27 }28 29 int bfs( int x1 , int y1 , int x2 , int y2 )30 {31     node now;32     q.push( node(x1,y1,key[x1][y1],0) );33     vis[x1][y1][ key[x1][y1] ] = true;    34     while( !q.empty() )35     {36         now = q.front();37         q.pop();38         if( now.x==x2 && now.y==y2 )39             return now.T;40         for( int i = 0 ; i<4 ; i++ )41         {42             int xx = now.x + dir[i][0];43             int yy = now.y + dir[i][1];44             if( xx>=1 && xx<=n && yy>=1 && yy<=m )45             {46                 int door = wall[xx][yy][now.x][now.y];47                 int kk = now.key | key[xx][yy];48                 if( !vis[xx][yy][kk] && ( door==-1 || ( door>=1 && ( (1<<door)&now.key )!=0 ) ) )49                 {50                     vis[xx][yy][kk] = true;51                     q.push( node(xx,yy,kk,now.T+1) );52                 }53             }54         }55     }56     return -1;57 }58 59 int main()60 {61     int p , k , s , g , q , x1 , x2 , y1 , y2 , ans;62     while( cin >> n >> m >> p )63     {64         cin >> k;65         init();66         while( k-- )67         {68             cin >> x1 >> y1 >> x2 >> y2 >> g;69             wall[x1][y1][x2][y2] = wall[x2][y2][x1][y1] = g;70         }71         cin >> s;72         while( s-- )73         {74             cin >> x1 >> y1 >> q;75             key[x1][y1] |= (1<<q);76         }77         ans = bfs( 1 , 1 , n , m );78         cout << ans << endl;79     }80     return 0;81 }