http://acm.hdu.edu.cn/showproblem.php?pid=1026
BFS+优先队列
我的代码
1 #include <cstdio>
2 #include <cstring>
3 #include <queue>
4 using namespace std;
5 typedef pair<int,int> pii;
6 priority_queue<pii,vector<pii>,greater<pii> >q;
7 const int N=110;
8 const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
9 char maze[N][N];
10 int dist[N][N],fa[N][N],vis[N][N],dir[N*N];
11 int m,n;
12 int ok(int x,int y)
13 {
14 return 0<=x && x<n && 0<=y && y<m && maze[x][y]!='X' && !vis[x][y];
15 }
16 void bfs(int x,int y)
17 {
18 while (!q.empty()) q.pop();
19 int d,nx,ny;
20 int u=x*m+y,v;
21 fa[x][y]=u;
22 vis[x][y]=1;
23 q.push(make_pair(dist[x][y],u));
24 while (!q.empty())
25 {
26 u=q.top().second; q.pop();
27 x=u/m; y=u%m;
28 for (d=0;d<4;d++)
29 {
30 nx=x+dx[d]; ny=y+dy[d];
31 if (ok(nx,ny))
32 {
33 vis[nx][ny]=1;
34 if (maze[nx][ny]=='.') dist[nx][ny]=dist[x][y]+1;
35 else dist[nx][ny]=dist[x][y]+maze[nx][ny]-'0'+1;
36 fa[nx][ny]=u;
37 if (vis[n-1][m-1]) return;
38 v=nx*m+ny;
39 q.push(make_pair(dist[nx][ny],v));
40 }
41 }
42 }
43 }
44 int main()
45 {
46 int i,j;
47 while (scanf("%d%d",&n,&m)!=EOF)
48 {
49 memset(dist,0,sizeof(dist));
50 memset(fa,0,sizeof(fa));
51 memset(vis,0,sizeof(vis));
52 for (i=0;i<n;i++) scanf("%s",maze[i]);
53 bfs(0,0);
54 if (!vis[n-1][m-1])
55 printf("God please help our poor hero.\n");
56 else {
57 printf("It takes %d seconds to reach the target position, let me show you the way.\n",dist[n-1][m-1]);
58 int u,c=0,cnt=0,dis,x,y,fx,fy;
59 for (u=n*m-1;fa[u/m][u%m]!=u;u=fa[u/m][u%m]) dir[++c]=u; dir[++c]=u;
60 x=dir[c]/m; y=dir[c]%m;
61 while (--c)
62 {
63 fx=x; fy=y;
64 x=dir[c]/m; y=dir[c]%m;
65 printf("%ds:(%d,%d)->(%d,%d)\n",++cnt,fx,fy,x,y);
66 while (cnt<dist[x][y]) printf("%ds:FIGHT AT (%d,%d)\n",++cnt,x,y);
67 }
68 }
69 printf("FINISH\n");
70 }
71 return 0;
72 }