HDU - 1026 Ignatius and the Princess I

題意：求在最短的時間內從左上角到右下角，每到達一個格子都要停留格子上的時間，每移動一次也都要一個單位時間，並打印每一秒所在的格子和路徑

思路：在BFS的基礎上還要加上優先隊列來求最短的時間

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 105;

struct node{
	int x,y;
	int step;
	friend bool operator <(node a,node b){
		return a.step > b.step;
	}
};
int d[4][2] = {{0,-1},{1,0},{0,1},{-1,0}};
char map[MAXN][MAXN];
int dir[MAXN][MAXN],v[MAXN][MAXN];
int n,m,tim,flag;

void print(int x,int y){
	if (x == 0 && y == 0)
		return;
	int nx = x - d[dir[x][y]][0];
	int ny = y - d[dir[x][y]][1];
	print(nx,ny);
	printf("%ds:(%d,%d)->(%d,%d)\n",tim++,nx,ny,x,y);
	while (v[x][y] > 0){
		printf("%ds:FIGHT AT (%d,%d)\n",tim++,x,y);
		v[x][y]--;
	}
}

void bfs(){
	memset(dir,-1,sizeof(dir));
	memset(v,-1,sizeof(v));
	priority_queue q;
	node s,tmp;
	int endx = n-1;
	int endy = m-1;
	s.x = 0,s.y = 0,s.step = 0;
	map[s.x][s.y] = 'X';
	q.push(s);
	while (!q.empty()){
		tmp = q.top();
		q.pop();
		if (tmp.x == endx && tmp.y == endy){
			flag = 1;
			printf("It takes %d seconds to reach the target position, let me show you the way.\n",tmp.step);
			tim = 1;
			print(endx,endy);
			return;
		}
		for (int i = 0; i < 4; i++){
			s = tmp;
			s.x += d[i][0];
			s.y += d[i][1];
			if (s.x < 0 || s.x >= n || s.y < 0 || s.y >= m || map[s.x][s.y] == 'X')
				continue;
			if (map[s.x][s.y] != '.'){
				s.step += map[s.x][s.y] - '0';
				v[s.x][s.y] = map[s.x][s.y] - '0';
			}
			s.step++;
			dir[s.x][s.y] = i;
			map[s.x][s.y] = 'X';
			q.push(s);
		}
	}
}

int main(){
	while (scanf("%d%d",&n,&m) != EOF){
		for (int i = 0; i < n; i++)
			scanf("%s",map[i]);
		flag = 0;
		bfs();
		if (!flag)
			printf("God please help our poor hero.\n");
		printf("FINISH\n");
	}
	return 0;
}