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

本文主要是介绍【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 , rconst 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 ;
}

这篇关于【HDU】5025 Saving Tang Monk 状压最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---