HDUOJ 1026 Ignatius and the Princess I（优先队列）(广搜）

优先队列广搜，经典广搜好题，建议都做做

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=110;
struct node{
	int x,y;
	int time;
	bool operator<(const node &b) const{
	return b.time<time;
	}
};
struct Pre{
	int px;
	int py;
}pre[maxn][maxn];
int dr[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int mp[maxn][maxn];
char str[maxn];
int visit[maxn][maxn];
int n,m;
const int INF=0x3f3f3f3f;


void bfs()
{
	node st,ed;
	priority_queue<node> q;
	while(!q.empty()) q.pop();

    st.x=n;st.y=m;
    st.time=mp[n][m];
    pre[n][m].px=-1;
    q.push(st);

    memset(visit,0,sizeof(visit));
    visit[n][m]=1;

    while(!q.empty())
    {
    	st=q.top();
    	q.pop();
    	if(st.x==1&&st.y==1)
    	{
    	     printf("It takes %d seconds to reach the target position, let me show you the way.\n",st.time);
			 int time=1;
			 int x=st.x,y=st.y;
			 int nx=pre[x][y].px,ny=pre[x][y].py;
			 while(pre[x][y].px!=-1)
			 {
			 	printf("%ds:(%d,%d)->(%d,%d)\n",time++,x-1,y-1,nx-1,ny-1);
			 	while(mp[nx][ny]--)
			 		printf("%ds:FIGHT AT (%d,%d)\n", time++, nx-1, ny-1);
			 	x=nx;y=ny;
			 	nx=pre[x][y].px;
			 	ny=pre[x][y].py;
			 }
			 printf("FINISH\n");
			 return ;
    	}
    	for(int i=0;i<4;i++)
    	{
    		ed.x=st.x+dr[i][0];
    		ed.y=st.y+dr[i][1];
    		if(mp[ed.x][ed.y]>=0&&!visit[ed.x][ed.y])
    		{
    			visit[ed.x][ed.y]=1;
    			ed.time=st.time+1+mp[ed.x][ed.y];
    			pre[ed.x][ed.y].px=st.x;
    			pre[ed.x][ed.y].py=st.y;

    			q.push(ed);
    		}
    	}
    }
    printf("God please help our poor hero.\n");
    printf("FINISH\n");
    return ;
}
int main()
{
    while(scanf("%d%d", &n,&m) != EOF)
    {
        gets(str);
        for(int i = 0; i <= n+1; i++)
            for(int j = 0; j <= m+1; j++)
                mp[i][j] = -1;

        char c;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                scanf("%c", &c);
                if(c != 'X')
                {
                    if(c == '.') mp[i][j] = 0;
                    else mp[i][j] = c-'0';
                }
            }
            gets(str);
        }

        bfs();
    }
    return 0;
}