首页 > ACM题库 > HDU-杭电 > HDU 3619-Heroes of Might and Magic-动态规划-[解题报告]HOJ
2014
11-29

HDU 3619-Heroes of Might and Magic-动态规划-[解题报告]HOJ

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

题意:给一个N*M的迷宫,迷宫有一个起点和一个终点,分别用S和T表示。迷宫中还有"#":障碍物,不能走; "."可以走,而且不费代价; “i”,其中i是大于1,小于9的数字,可以走,但是要费一定的代代价,所花的代价就是数字i的值。;"A、B、C、D、E":其中的一种,表示该位置放置了一把锁,需要钥匙才能进入该点,钥匙的位置由题意给出。求从起点到终点的最少花费。

思路:用状态dp[i][j][k]表示从(i,j)点到终点的最少花费, 且此时拥有的钥匙的情况是k,这样很容易就想到可以用动态规划求解,而且复杂度也不会超时, 状态方程为:dp[i][j][k] = MIN( dp[i'][j'][k']  + cost) 其中(i’ , j‘)为从(i,j)可以合法达到的点,k’新的钥匙情况,cost为花费,这样就可以用记忆化搜索解决,似乎这样的思路没有问题。 其实一开始我也是这么认为的,但是这样处理这个问题还是有一个问题存在的,
那就是记忆化搜索! 前面的状态表示法没有问题,但是在记忆化搜索的时候,因为任意两个点之间的搜索先后顺序是任意可能的,但是我们所要求的最短路的方向是一定的,假设我们最后确定的最短路的方向是(i,j) – > (i’ , j’) (这里值枚举两个点来说明),理想的记忆化的方向是要求(i,j)的最短路, 现在我们可以先求出( i’ , j’)的最短路,然后加上这段的代价就可以得出(i,j)的最短路。但是因为在记忆化的过程中, 我先到了(i’,j’)点, 现在我先要求改点的最短路,同样地,我们要先求出其四周围的点的最短路,其中当然包括(i,j)
,此时(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 ;
}

参考:http://blog.csdn.net/ivan_zjj/article/details/7434449


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