|
t stud{ stud(int xx,int yy,int s):x(xx),y(yy),step(s){}; stud(){}; int x,y,step; bool operator<(const stud b) const { return step>b.step; } }; int n,m; priority_queue
q; int path[N][N]; int vis[N][N]; int step[4][2]={1,0,-1,0,0,1,0,-1}; int all; char c[N][N]; bool judge(int x,int y) { if(x>=0&&x
=0&&y
(%d,%d) ,++all,xx,yy,x,y); if(c[x][y]>='0'&&c[x][y]<='9') { int i=c[x][y]-'0'; while(i--) printf(%ds:FIGHT AT (%d,%d) ,++all,x,y); } } bool bfs() { int i,j; stud cur,next; while(!q.empty()) q.pop(); mem(vis,0); vis[0][0]=1; cur.x=0; cur.y=0; cur.step=0; q.push(cur); while(!q.empty()) { cur=q.top(); q.pop(); if(cur.x==n-1&&cur.y==m-1) { printf(It takes %d seconds to reach the target position, let me show you the way. ,cur.step); all=0; show(n-1,m-1); return true; } for(i=0;i<4;i++) { int xx=cur.x+step[i][0]; int yy=cur.y+step[i][1]; if(!judge(xx,yy)) continue; if(vis[xx][yy]) continue; if(c[xx][yy]=='X') continue; next.x=xx; next.y=yy; next.step=cur.step+1; if(c[xx][yy]>='0'&&c[xx][yy]<='9') next.step+=c[xx][yy]-'0'; q.push(next); vis[xx][yy]=cur.step+1; path[xx][yy]=i; } } return false; } int main() { int i,j; while(~scanf(%d%d,&n,&m)) { for(i=0;i
?
?
|