hdu 4771 Stealing Harry Potter's Precious

点击打开链接

题意：题目给定一个n*m的地图，地图有一个起点标记为'@'，还有'#'表示不能够走的，'.'表示可以走。给定k个点，问从起点开始把这k个点走过去的最小步数。

思路：题目k的最大为4，那么我们就可以直接暴力k个点的走的顺序，然后利用bfs即可

代码：

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 110;

int n , m , k;
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
char mat[MAXN][MAXN];

struct Node{
	int x;
	int y;
	int step;
};
Node start;
Node node[5]; 

bool isOk(int x , int y){
	if(x >= 1 && x <= n && y >= 1 && y <= m)
		return true;
	return false;
}

int bfs(Node begin , Node end){

    queue<Node>q;
	bool vis[MAXN][MAXN];
	memset(vis , false , sizeof(vis));
	begin.step = 0;
	q.push(begin);
	vis[begin.x][begin.y] = true;

	while(!q.empty()){
		Node tmp = q.front();
		q.pop();
		if(tmp.x == end.x && tmp.y == end.y)
			return tmp.step;
		for(int i = 0 ; i < 4 ; i++){
			int x = tmp.x+dir[i][0];
			int y = tmp.y+dir[i][1];
			if(isOk(x , y) && !vis[x][y] && mat[x][y] == '.'){
				q.push((Node){x , y , tmp.step+1});
				vis[x][y] = true;
			}
		}
	}
	return INF;
}

void solve(){
    int tmp[5];
	int ans = INF;
	for(int i = 0 ; i < k ; i++)
		tmp[i] = i+1;

    int step = bfs(start , node[tmp[0]]);
    for(int i = 1 ; i < k ; i++) 
		step += bfs(node[tmp[i-1]] , node[tmp[i]]);
    ans = min(ans , step); 

	while(next_permutation(tmp , tmp+k)){
		int step = bfs(start , node[tmp[0]]);
		for(int i = 1 ; i < k ; i++) 
			step += bfs(node[tmp[i-1]] , node[tmp[i]]);
		ans = min(ans , step); 
	}
	printf("%d\n" , ans == INF ? -1 : ans);
}

int main(){
    while(scanf("%d%d%*c" , &n , &m) && n+m){
		for(int i = 1 ; i <= n ; i++){
			for(int j = 1 ; j <= m ; j++){
                scanf("%c" , &mat[i][j]);
                if(mat[i][j] == '@'){
					start = (Node){i , j , 0};
				}
			}
			getchar();
		}
        scanf("%d" , &k);
		for(int i = 1 ; i <= k ; i++)
			scanf("%d%d" , &node[i].x , &node[i].y);
		solve();
	}
	return 0;
}