【HDU】5025 Saving Tang Monk 状压最短路

传送门：【HDU】5025 Saving Tang Monk

题目分析：这题一开始想都没想就敲了优先队列+dij。。然后TLE了。。。

后来发现是一个稀疏图。。换成spfa就过了。。

这是一个四维最短路，x轴，y轴，拿到第几个钥匙，打怪的状态（状压），然后就是很简单的状压最短路了。

要注意到钥匙不用状压，因为拿到钥匙是有顺序的。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define root 1 , 1 , n
#define rt o , l , r

const int MAXN = 105 ;
const int MAXQ = 3000005 ;
const int INF = 0x3f3f3f3f ;

struct Node {
int x , y , u , s ;
Node () {}
Node ( int x , int y , int u , int s ) : x ( x ) , y ( y ) , u ( u ) , s ( s ) {}
} Q[MAXQ] ;

int head , tail ;
char G[MAXN][MAXN] ;
int d[MAXN][MAXN][10][33] ;
int map[MAXN][MAXN] ;
bool vis[MAXN][MAXN][10][33] ;
int path[4][2] = { { 1 , 0 } , { -1 , 0 } , { 0 , 1 } , { 0 , -1 } } ;
int sx , sy ;
int ex , ey ;
int n , m ;

int dijkstra () {
int ans = INF ;
clr ( d , INF ) ;
head = tail = 0 ;
d[sx][sy][0][0] = 0 ;
Q[tail ++] = Node ( sx , sy , 0 , 0 ) ;
while ( head != tail ) {
Node now = Q[head ++] ;
if ( head == MAXQ ) head = 0 ;
if ( now.u == m && now.x == ex && now.y == ey ) {
ans = min ( ans , d[now.x][now.y][now.u][now.s] ) ;
continue ;
}
vis[now.x][now.y][now.u][now.s] = 0 ;
rep ( i , 0 , 4 ) {
int nx = now.x + path[i][0] ;
int ny = now.y + path[i][1] ;
if ( nx < 0 || nx >= n || ny < 0 || ny >= n || G[nx][ny] == '#' ) continue ;
int nu = now.u ;
int ns = now.s ;
int nd = 1 ;
if ( G[nx][ny] == 'S' ) {
if ( ! ( ns & ( 1 << map[nx][ny] ) ) {
ns |= ( 1 << map[nx][ny] ) ;
++ nd ;
}
}
if ( G[nx][ny] <= '9' && G[nx][ny] > '0' ) {
int tmp = G[nx][ny] - '0' ;
if ( tmp == nu + 1 ) ++ nu ;
}
if ( d[nx][ny][nu][ns] > d[now.x][now.y][now.u][now.s] + nd ) {
d[nx][ny][nu][ns] = d[now.x][now.y][now.u][now.s] + nd ;
if ( !vis[nx][ny][nu][ns] ) {
Q[tail ++] = Node ( nx , ny , nu , ns ) ;
if ( tail == MAXQ ) tail = 0 ;
vis[nx][ny][nu][ns] = 1 ;
}
}
}
}
return ans == INF ? -1 : ans ;
}

void solve () {
int cnt = 0 ;
clr ( vis , 0 ) ;
rep ( i , 0 , n ) {
scanf ( "%s" , G[i] ) ;
rep ( j , 0 , n ) {
if ( G[i][j] == 'K' ) {
sx = i ;
sy = j ;
} else if ( G[i][j] == 'T' ) {
ex = i ;
ey = j ;
} else if ( G[i][j] == 'S' ) {
map[i][j] = cnt ++ ;
}
}
}
int step = dijkstra () ;
if ( ~step ) printf ( "%d\n" , step ) ;
else printf ( "impossible\n" ) ;
}

int main () {
while ( ~scanf ( "%d%d" , &n , &m ) && ( n || m ) ) solve () ;
return 0 ;
}