将起始点、终点和钥匙统一编号，预处理：
1.起始点到所有钥匙+终点的最短路
2.所有钥匙之间两两的最短路
3.所有钥匙到终点的最短路
将起始点和所有钥匙四方向出发设为起点BFS一遍，求出它到任意点任意方向的最短路dp[i][j][k]。（即到点(i,j)且方向为k的最短路），BFS时需要注意：
1.UDLR有可能组成死循环
2.转向符在墙边并且指向了墙时，无法重新选择方向。例如这个： S...L#E
3.只有豆腐块滑动碰到墙停止了之后，才能把这个点的坐标加入队列。在滑动过程中经过的点都不需要加入队列。
4.钥匙在墙边的情况。在一次滑动过程中，豆腐块经过K时只有一个方向。但是如果K在墙边，并且滑动方向可以使豆腐块在K的位置停住，那么在这个K的位置，豆腐块向四方向移动的状态都是可达的。
例如：S.....E......K#
在我的方法中，如果不特殊处理的话，会出现经过K时，只有向右的状态是可达的，其它方向都不可达。但是实际上，从K开始向上下左右的状态显然都是合法状态，都可以达到。
5.遇到强制转向符号的时候step是不会增加的，只有在墙边停止下来重新选择方向的时候step才+1
KtoK[i][j][x][y]表示起始点为 i 方向为x到终点为j方向为y的最短路
用二进制表示得到钥匙的状态，一共7把钥匙，2^7种状态。
ans[x][y][z]表示得到钥匙的状态为x，经过的最后一把钥匙为y且此时方向为z的最短路。
ans[x][y][z] = min( ans[ x ^ ( 1 << y ) ][ k ][ m ] + KtoK[k][y][m][z] );
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <queue>
using namespace std; const int MAXN = 210; const int INF = 1 << 20; const int dx[] = { -1, 1, 0, 0 };//上下左右 const int dy[] = { 0, 0, -1, 1 }; struct Point { int x, y; int move; //最小步数 int toward; //当前朝向 bool st; Point( int x = 0, int y = 0, int mv = 0, int ct = 0, int to = 0, bool st = false ): x(x), y(y), move(mv), toward(to), st(st) { } }; int R, C; int dp[MAXN][MAXN][4]; int KtoK[10][10][4][4]; //钥匙i到钥匙j起始方向为x终止方向为y的最短路 int ans[ 1 << 8 ][10][4]; char mat[MAXN][MAXN]; int cntK; //钥匙个数 Point start, end, Key[8]; void init() { for ( int i = 0; i < 10; ++i ) for ( int j = 0; j < 10; ++j ) for ( int m = 0; m < 4; ++m ) for ( int n = 0; n < 4; ++n ) KtoK[i][j][m][n] = INF; cntK = 1; for ( int i = 1; i <= R; ++i ) for ( int j = 1; j <= C; ++j ) { switch ( mat[i][j] ) { case 'S': start.x = i, start.y = j; break; case 'E': end.x = i, end.y = j; break; case 'K': Key[cntK].x = i, Key[cntK].y = j, ++cntK; break; } } Key[0] = start; Key[cntK] = end; return; } bool check( int x, int y ) { return x > 0 && x <= R && y > 0 && y <= C; } int BFS( Point st ) { //printf("st(%d, %d)to%d ed(%d, %d)to%d ", st.x, st.y, st.toward, ed.x, ed.y, ed.toward ); for ( int i = 0; i < MAXN; ++i ) for ( int j = 0; j < MAXN; ++j ) for ( int k = 0; k < 4; ++k ) dp[i][j][k] = INF; dp[ st.x ][ st.y ][ st.toward ] = 0; queue<Point> Q; Q.push(st); while ( !Q.empty() ) { Point p = Q.front(); Q.pop(); //printf("====%d %d ", p.x, p.y ); int len = p.st ? p.toward : 3; for ( int i = p.st ? p.toward : 0; i <= len; ++i ) { int xx = p.x, yy = p.y; if ( !check( xx + dx[i], yy + dy[i] ) ) continue; if ( mat[ xx + dx[i] ][ yy + dy[i] ] == '#' ) continue; bool ok = true; int toward = i; while ( mat[xx][yy] != '#' ) { //printf("%d %d %d ", xx, yy, p.st ); switch( mat[xx][yy] ) { case 'U': toward = 0; break; case 'D': toward = 1; break; case 'L': toward = 2; break; case 'R': toward = 3; break; default: break; } xx += dx[toward]; yy += dy[toward]; if ( !check( xx, yy ) ) { ok = false; break; } int &res = dp[xx][yy][toward]; //printf( "%d dp[%d][%d][%d]=%d, %d ", ok, xx, yy, toward, res, p.move + 1 ); if ( ok && p.move < res ) { res = p.move; if ( check( xx + dx[toward], yy + dy[toward] ) ) { if ( mat[ xx + dx[toward] ][ yy + dy[toward] ] == '#' ) { if ( mat[xx][yy] != 'L' && mat[xx][yy] != 'R' && mat[xx][yy] != 'U' && mat[xx][yy] != 'D' ) { if ( mat[xx][yy] == 'K' ) //特殊处理K在墙边的情况 { for ( int k = 0; k < 4; ++k ) dp[xx][yy][k] = min( dp[xx][yy][k], p.move + 1 ); } Q.push( Point( xx, yy, p.move + 1, 0, false ) ); } } } } else break; //之前少了这句话，一直TLE } } } return INF; } int main() { //freopen("1006.in","r",stdin); //freopen("out.txt","w",stdout); while ( ~scanf( "%d%d", &R, &C ) ) { for ( int i = 1; i <= R; ++i ) scanf( "%s", &mat[i][1] ); init(); //预处理所有钥匙之间的最短路 for ( int i = 0; i < cntK; ++i ) { for ( int k = 0; k < 4; ++k ) { Point st = Key[i]; st.move = 0; st.st = true; st.toward = k; BFS( st ); for ( int j = 0; j <= cntK; ++j ) for ( int m = 0; m < 4; ++m ) { if ( i == j && k == m ) { KtoK[i][j][k][m] = 0; continue; } KtoK[i][j][k][m] = dp[ Key[j].x ][ Key[j].y ][m]; //printf( "KtoK[%d][%d][%d][%d] = %d ", i, j, k, m, KtoK[i][j][k][m] ); } } } for ( int i = 0; i < ( 1 << ( cntK - 1 ) ); ++i ) for ( int j = 0; j < cntK; ++j ) for ( int k = 0; k < 4; ++k ) ans[i][j][k] = INF; for ( int i = 0; i < 4; ++i ) ans[0][0][i] = 1; for ( int i = 0; i < ( 1 << ( cntK - 1 ) ); ++i ) for ( int j = 0; j < cntK; ++j ) for ( int k = 0; k < 4; ++k ) { int v = ans[i][j][k]; if ( v == INF ) continue; for ( int y = 1; y < cntK; ++y ) for ( int z = 0; z < 4; ++z ) { int x = ( i | ( 1 << ( y - 1 ) ) ); if ( ans[x][y][z] > v + KtoK[j][y][k][z] ) ans[x][y][z] = v + KtoK[j][y][k][z]; } } int aa = INF; for ( int i = 0; i < cntK; ++i ) for ( int j = 0; j < 4; ++j ) for ( int k = 0; k < 4; ++k ) { aa = min( aa, ans[ ( 1 << ( cntK - 1 ) ) - 1 ][i][j] + KtoK[i][cntK][j][k] ); } if ( aa >= INF ) aa = -1; printf( "%d ", aa ); } return 0; }