学步园

1026 Ignatius and the Princess I

http://acm.hdu.edu.cn/showproblem.php?pid=1026

这道题是经典的地图寻路搜索问题

可以用广度优先搜索来完成此题

AC CODE：

#include <stdio.h><br /> #include <string.h><br /> const int MaxQueue = 1010000;<br /> char g[105][105];<br /> int v[105][105];<br /> int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};<br /> int n,m,flagForEnd,second;<br /> struct Node<br /> {<br /> int x,y; //position<br /> int time;<br /> int last; // the last step before<br /> }state[MaxQueue],temp;<br /> void bfs(),init();<br /> void output(int t)<br /> {<br /> if (state[t].last == -1) //如果是第一个点<br /> {<br /> // printf("1s:(0,0)->");<br /> return;<br /> }<br /> output(state[t].last);<br /> second++;<br /> // if (state[t].last == 0) {printf("(%d,%d)/n",state[t].x,state[t].y);return;}<br /> // if (state[t].x == state[state[t].last].x && state[t].y == state[state[t].last].y) //fight<br /> // printf("%ds:FIGHT AT (%d,%d)/n",second,state[t].x,state[t].y);<br /> if (g[state[t].x][state[t].y]!='.' && g[state[t].x][state[t].y]!='X')<br /> {<br /> printf("%ds:(%d,%d)->(%d,%d)/n",second++,state[state[t].last].x,state[state[t].last].y,state[t].x,state[t].y);<br /> int hp = g[state[t].x][state[t].y] - '0';<br /> int i;<br /> for (i=0;i<hp;i++) printf("%ds:FIGHT AT (%d,%d)/n",second++,state[t].x,state[t].y);<br /> second--;<br /> }<br /> else<br /> printf("%ds:(%d,%d)->(%d,%d)/n",second,state[state[t].last].x,state[state[t].last].y,state[t].x,state[t].y);<br /> }<br /> int main()<br /> {<br /> int i,j;<br /> while (scanf("%d %d",&n,&m)!=EOF)<br /> {<br /> for (i=0;i<n;i++)<br /> {<br /> scanf("%s",g[i]);<br /> }<br /> init();<br /> //printf("%d",v[0]);<br /> bfs();<br /> if (v[n-1][m-1] > 10000)<br /> printf("God please help our poor hero./nFINISH/n");<br /> else<br /> {<br /> printf("It takes %d seconds to reach the target position, let me show you the way./n",v[n-1][m-1]);<br /> second = 0;<br /> output(flagForEnd);<br /> printf("FINISH/n");<br /> }<br /> }<br /> //getchar();<br /> return 0;<br /> }</p> <p>void bfs()<br /> {<br /> int i,head = 0,tail = 1;<br /> state[head].x = 0; state[head].y =0; state[head].time = 0; state[head].last = -1;<br /> v[0][0] = 0;<br /> while (head!=tail && tail!=MaxQueue-5)<br /> {<br /> temp = state[head];<br /> for (i=0;i<4;i++) //search for the 4 direction<br /> {<br /> int tx = temp.x + dir[i][0];<br /> int ty = temp.y + dir[i][1];<br /> if (tx >= 0 && tx < n && ty >=0 && ty < m && g[tx][ty]!='X')<br /> {<br /> int plus;<br /> if (g[tx][ty] == '.') plus = 1;<br /> else plus = g[tx][ty]-'0' + 1;<br /> if (temp.time+plus < v[tx][ty]) // 如果有更小步数的走法<br /> {<br /> if (tx == n-1 && ty == m-1) flagForEnd = tail;<br /> state[tail].x = tx; state[tail].y = ty;<br /> v[tx][ty] = temp.time + plus;<br /> state[tail].time = v[tx][ty];<br /> state[tail].last = head;<br /> tail++;<br /> }<br /> }<br /> }<br /> head++;<br /> }<br /> }<br /> void init()<br /> {<br /> memset(v,1,sizeof(v));<br /> }<br />