2014
11-29

# Heroes of Might and Magic

After a very long journey and uncountable number of uphill battles, hero Raelag (who is the transformed Agrael, notice that "Raelag" is an anagram of "Agrael") finally find the map shows where the "Holy Cap" is. Now he is going to find the treasure.

The map is made up of squares of equal size which are arranged in r rows and c columns. At the beginning, Raelag is at the square Labeled ‘S’, and the "Holy Cap" is at the square Labeled ‘T’. It is guarranteed that there is only one ‘S’ and only one ‘T’ in a map. Squares that labeled with ‘#’ in the map means squares that can’t be passed; ‘.’ means roads that can be passed without any physical loss and squares that labeled with an integer i (1 ≤ i ≤ 9) means when Raelag pass through this square, he will suffer i points of physical loss. Squares that labeled with capital letter ‘A’, ‘B’, ‘C’, ‘D’ or ‘E’ means doors that can be passed only if Raelag has the right key (There are at most 5 kinds of doors in a map). The squares labeled with ‘S’, ‘T’ and other capital letters all can be passed with out physical loss. Raelag can move to squares only if that square share an edge with the square he is now in. Raelag can’t move out of the map.

The fist line of input file contains a single integer T (1 ≤ T ≤ 10) – the number of test cases. For each test case, in the first line their are three integers: r, c and k (1 ≤ r, c ≤ 50, 0 ≤ k ≤ 5), representing the hight, length of the map and the number of kinds of doors in the map. Then there are r lines giving the map. Then k lines follows giving the position of the keys to the door ‘A’, ‘B’, ‘C’, ‘D’, and ‘E’ in order.

The uperleft conner is row 1 and colomn 1.

The fist line of input file contains a single integer T (1 ≤ T ≤ 10) – the number of test cases. For each test case, in the first line their are three integers: r, c and k (1 ≤ r, c ≤ 50, 0 ≤ k ≤ 5), representing the hight, length of the map and the number of kinds of doors in the map. Then there are r lines giving the map. Then k lines follows giving the position of the keys to the door ‘A’, ‘B’, ‘C’, ‘D’, and ‘E’ in order.

The uperleft conner is row 1 and colomn 1.

2
3 3 1
S21
#A#
11T
1 3
3 5 2
S..A.
##.##
.B.AT
3 1
1 5

6
-1

http://acm.hdu.edu.cn/showproblem.php?pid=3619

，此时（i,j）的最短路一定还没有求出（这是因为若是已求出，则（i’ ，j‘
）的最短路也会一定已求出），那么就要先求出（i,j ）的最短路，但是求(i,j)的最短路的时候，我们又要用到(i’,j’)的最短路，此时(i’,j’)的最短路，是没有被正确求出的，只有用了一个INF表示，但是(i,j)点以为（i’,j’）点的最短路已经求出， 因此直接返回， 这样最终得出的(i,j)点的最短路就会是错误的， 因此（i’，j’）的最短路也将是错误的，从而导致结果出错。

这样就让我们不禁会想，到底什么时候能用记忆化搜索。从上面的问题我们可以看出，其实出问题的地方就在于记忆化搜索的方向问题， 上面的例子中，就是两个点可以以任意的方向搜索，这样就会出现问题了。回想记忆化搜索的经典例子：滑雪。那个例子之所以可以用记忆化搜索，就是因为任意两个点有高度差， 因此搜索是带有方向性 的，所以可以保证结果的准确性。

好了，回到本题上， 这题正确的解放应该是：用spfa在上述表示的状态下求最短路。只不过这个并不再是一维的spfa，但是实质是一样的。具体请见代码

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
#define MIN(a,b) (a)>(b)?(b):(a)
const int INF = 0x3f3f3f3f ;
int T ,N ,M , K ,Sr,Sc,Er,Ec;
char maze[55][55] ;
unsigned int MA ;
int dr[4] = {-1, 1, 0, 0} ;
int dc[4] = {0,0,-1,1} ;
int key[51][51] ;
queue<int> que ;
bool in[55][55][1<<5] ;
int dis[55][55][1<<5] ;
bool relax(int r,int c ,int s ,int nr,int nc , int ns, int d){
if(dis[nr][nc][ns] > dis[r][c][s] + d){
dis[nr][nc][ns] = dis[r][c][s] + d ;
return true;
}
return false ;
}

void spfa(){
MA = (1 << K) - 1 ;
while(!que.empty()) que.pop() ;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
for(int k=0;k<=MA;k++){
in[i][j][k] = 0 ;
dis[i][j][k] = INF ;
}
}
}
dis[Sr][Sc][0] = 0 ;
in[Sr][Sc][0] = 1 ;
que.push(Sr);	que.push(Sc); que.push(0);
while(!que.empty()){
int r = que.front() ; que.pop() ;
int c = que.front() ; que.pop() ;
int s = que.front() ; que.pop() ;
in[r][c][s] = 0 ;
for(int i=0;i<4;i++){
int nr = r + dr[i] ;
int nc = c + dc[i] ,ns;
if(nr<1||nc<1||nr>N||nc>M||maze[nr][nc]=='#')	continue ;
ns = (s | key[nr][nc]) ;
if(maze[nr][nc]=='.'){
if(relax(r,c,s, nr,nc,ns,0) && !in[nr][nc][ns]){
in[nr][nc][ns] = 1 ;
que.push(nr) ; que.push(nc) ;que.push(ns) ;
}
}
else if(maze[nr][nc]>='1' && maze[nr][nc]<='9'){
if(relax(r,c,s, nr,nc,ns , maze[nr][nc]-'0') && !in[nr][nc][ns]){
in[nr][nc][ns] = 1 ;
que.push(nr) ; que.push(nc) ;que.push(ns) ;
}
}
else{
int a = maze[nr][nc] - 'A' ;
if((s&(1<<a)) != 0){			//需要有钥匙才能进入
if(relax(r,c,s, nr,nc,ns ,0) && !in[nr][nc][ns]){
in[nr][nc][ns] = 1 ;
que.push(nr) ; que.push(nc) ;que.push(ns) ;
}
}
}
}
}
int ans = INF ;
for(int i=0;i<=MA;i++){
if(ans > dis[Er][Ec][i]){
ans = dis[Er][Ec][i] ;
}
}
if(ans == INF){
ans = -1 ;
}
printf("%d\n",ans);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&N,&M,&K);
for(int i=1;i<=N;i++){
scanf("%s",maze[i]+1);
for(int j=1;j<=M;j++){
if(maze[i][j]=='S'){
Sr = i ; Sc = j ;
maze[i][j] = '.' ;
}
if(maze[i][j] == 'T'){
Er = i ; Ec = j ;
maze[i][j] = '.' ;
}
}
}
memset(key , 0 ,sizeof(key));
for(int i=0;i<K;i++){
int a ,b ;
scanf("%d %d",&a , &b);
key[a][b] = (key[a][b] | (1<<i)) ;		//存放每个点的钥匙情况
}
spfa() ;
}
return 0 ;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。