1026 优先队列+dfs(诸多不懂)

myhalfsea posted @ 2010年3月16日 04:24 in 未分类 , 915 阅读

#include<iostream>
#include<queue>
using namespace std;

struct node {
    int x,y;
    int time;
    bool operator< (const node t) const {
        return time>t.time;
    }
};

struct cmap {
    int nx,ny;
    char c;
}map[101][101];

int n,m;
int fight[101][101], mark[101][101];
priority_queue<node> que;

int bfs() {
    int k;
    int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
    node now,next;
    while(!que.empty())
        que.pop();
    now.x=n-1;now.y=m-1;
    if(map[now.x][now.y].c>='1' && map[now.x][now.y].c<='9') {
        now.time=map[n-1][m-1].c-'0';
        fight[now.x][now.y]=map[now.x][now.y].c-'0';
    }
    else
        now.time=0;
    que.push(now);
    while(!que.empty()) {
        now=que.top();
        que.pop();
        if(now.x==0 && now.y==0)
            return now.time;
        for(k=0;k<4;k++) {
            next.x=now.x+dir[k][0];
            next.y=now.y+dir[k][1];
            if(next.x>=0 && next.x<n && next.y>=0 && next.y<m && !mark[next.x][next.y] && map[next.x][next.y].c!='X') {
                if(map[next.x][next.y].c>='1' && map[next.x][next.y].c<='9') {
                    fight[next.x][next.y]=map[next.x][next.y].c-'0';
                    next.time=now.time+map[next.x][next.y].c-'0'+1;
                }
                else
                    next.time=now.time+1;
                que.push(next);
                map[next.x][next.y].nx=now.x;
                map[next.x][next.y].ny=now.y;
                mark[next.x][next.y]=1;
            }
        }
    }
    return -1;
}


int main()
{
    int i,j,flag,x,y,tx,ty,sec;
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF) {
        for(i=0;i<n;i++) {
            for(j=0;j<m;j++) {
                scanf(" %c",&map[i][j].c);
                mark[i][j]=fight[i][j]=0;
            }
        }
        mark[n-1][m-1]=1;
        flag=bfs();
        if(flag!=-1){
            printf("It takes %d seconds to reach the target position, let me show you the way.\n",flag);
            sec=1;x=y=0;
            while(sec!=flag+1) {
                printf("%ds:(%d,%d)->(%d,%d)\n",sec++,x,y,map[x][y].nx,map[x][y].ny);
                for(i=1;i<=fight[map[x][y].nx][map[x][y].ny];i++)
                    printf("%ds:FIGHT AT (%d,%d)\n",sec++,map[x][y].nx,map[x][y].ny);
                tx=map[x][y].nx;ty=map[x][y].ny;
                x=tx;y=ty;
            }
        }
        else
            printf("God please help our poor hero.\n");
        printf("FINISH\n");
    }
    return 0;
}


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta
Butterfly Theme | Design: HRS Hersteller of mobile Hundeschule.