Collect Chars
Time Limit:2 Seconds Memory Limit:65536 KB
Bob was playing MC and was punished by Alice. Bob was trapped in a maze and there were some characters on some specific cells. When he walks on a specific point, he will pick up the character automatically (he cannot refuse to do that) and push back the character in his bag (You can treat it as adding a character to the end of a string and initially, the string is empty.). Alice has set several goal strings and when Bob’s bag contains any one of the strings, Bob is enabled to return to the true world.
Bob can walk to the adjacent cell (up, down, left, right) at one time, and it costs no time to pick up the character and the character won’t disappear, which means if Bob want’s he can get endless characters once he walked on the certain cell but he must pick up at least one character.
Bob wants to leave the maze as soon as possible, and he asks you for the shortest time that he can go out of that maze.
Input
The first line is an integern, indicating the number of testcases.
In each case, the first line is two integersLandC(0 <L,C≤ 20). After this,Llines follow, and each hasCcharacters. For each character, ‘.’ stands for an open space, ‘#’ stands for a wall which cannot be crossed, ‘@’ stands for the beginning point of the maze. All capital letters ‘A’ to ‘Z’ stand for the characters which can be picked up.
After that, there is one integerW, which means the number of goal strings (0 <W≤ 200). AndWlines following, each line has a string, containing letters ‘A’ to ‘Z’ only, which length is less than 100.
Output
For each case, you should output an integer. The answer is the minimum time that Bob must use to get out of the maze. If he can’t do that, you should output -1.
Sample Input25 5A.DB#@#.##.#..C.#……..3ABACBC5 5A.DB#@#.##.#..C.#……..2AADBBBDCCACSample Output119Hint
In the first sample, Bob will get "AC" as for goal string. And in the second sample, Bob will get "AADBBBDCC" as for goal string.
题目大意：给出地图，地图中有一些字符，每走过的字母都可以拾取若干个，形成一个串，给出w个串，，如果形成的串中包含了w个串中的一个，那么就可以跳出，输出最少的步数，否则-1
第一步，对每一个字符给定一个编号，bfs搜索出每个字符可以直接到达的其他字符的最短路径。
第二步，找出开始@到所有字符的最短路径
第三步，对于给出的串，进行dp，dp[i][j]代表走到串的第i个字符，为图中对应编号为j的字符的最小步数。先使用第二步中得到到达第一个字符的最短路径进行初始化，然后使用第一步中的到最短路径进行dp，最后得到最小的值。
#include <cstdio>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <map>#include <vector>#include <algorithm>#define INF 0x3f3f3f3f#define LL long longusing namespace std ;int c[410][410] , n , m ;vector <int> vec[30] ;char str[110] ;char Map[30][30] ;int flag[30][30] ;int a[4][2] = { {0,-1},{0,1},{-1,0},{1,0} } ;LL ans ;struct node{int x , y , t ;} ;queue <node> que ;void bfs(int x,int y) {memset(flag,0,sizeof(flag)) ;int k , i , j ;k = x*n+y ;node p , q ;p.x = x ; p.y = y ;p.t = 0 ;flag[x][y] = 1 ;while( !que.empty() ) que.pop() ;que.push(p) ;while( !que.empty() ) {p = que.front() ;que.pop() ;for(i = 0 ; i < 4 ; i++) {q = p ;q.t++ ;q.x += a[i][0] ;q.y += a[i][1] ;if( q.x >= 0 && q.x < n && q.y >= 0 && q.y < m && Map[q.x][q.y] != '#' && flag[q.x][q.y] == 0 ) {flag[q.x][q.y] = 1 ;if( Map[q.x][q.y] == '.' || Map[q.x][q.y] == '@' )que.push(q) ;elsec[k][ q.x*n+q.y ] = q.t ;}}}}int temp[410] ;void b(int x,int y){memset(flag,0,sizeof(flag)) ;memset(temp,INF,sizeof(temp)) ;int i , j ;node p , q ;p.x = x ;p.y = y ;p.t = 0 ;flag[x][y] = 1 ;while( !que.empty() ) que.pop() ;que.push(p) ;while( !que.empty() ) {p = que.front() ;que.pop() ;for(i = 0 ; i < 4 ; i++) {q = p ;q.t++ ;q.x += a[i][0] ;q.y += a[i][1] ;if( q.x >= 0 && q.x < n && q.y >= 0 && q.y < m && Map[q.x][q.y] != '#' && flag[q.x][q.y] == 0 ) {flag[q.x][q.y] = 1 ;if( Map[q.x][q.y] == '.' || Map[q.x][q.y] == '@' )que.push(q) ;else {temp[ q.x*n+q.y ] = q.t ;que.push(q) ;}}}}}int dp[110][410] ;int main() {int t , w , i , j , l , k , x , y ;scanf("%d", &t) ;while( t– ) {memset(c,INF,sizeof(c)) ;for(i = 0 ; i < 410; i++)c[i][i] = 0 ;scanf("%d %d", &n, &m) ;for(i = 0 ; i < n ; i++) {scanf("%s", Map[i]) ;}for(i = 0 ; i < 30 ; i++)vec[i].clear() ;for(i = 0 ; i < n ; i++) {for(j = 0 ; j < m ; j++) {if( Map[i][j] != '#' && Map[i][j] != '.' ) {if( Map[i][j] == '@' ) {k = i*n+j ;x = i , y = j ;}else vec[ Map[i][j]-'A' ].push_back(i*n+j) ;bfs(i,j) ;}}}b(x,y) ;scanf("%d", &w) ;ans = INF ;int h , u , v ;while( w– ) {scanf("%s", str) ;l = strlen(str) ;memset(dp,INF,sizeof(dp)) ;for(i = 0 ; i < vec[ str[0]-'A' ].size() ; i++){dp[0][i] = temp[ vec[ str[0]-'A' ][i] ] ;}for(i = 1 ; i < l ; i++) {for(j = 0 ; j < vec[str[i]-'A'].size() ; j++) {for(h = 0 ; h < vec[ str[i-1]-'A' ].size() ; h++) {dp[i][j] = min( dp[i][j],dp[i-1][h]+c[ vec[ str[i-1]-'A'][h] ][ vec[ str[i]-'A'][j] ] ) ;}}}for(i = 0 ; i < vec[str[l-1]-'A'].size() ; i++)if( dp[l-1][i] < ans ) ans = dp[l-1][i] ;}if( ans == INF )printf("-1\n") ;elseprintf("%lld\n", ans) ;}return 0 ;}
生活若剥去了理想梦想幻想，那生命便只是一堆空架子
