• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-65  評論-6  文章-0  trackbacks-0
              1 #include<iostream>
              2 #include<queue>
              3 #include<algorithm>
              4 #include<stack>
              5 using namespace std;
              6 #define MAXSIZE 100
              7 struct node{
              8     int x,y,ti;
              9     node(int _x=0,int _y=0,int _ti=0):x(_x),y(_y),ti(_ti){};
             10     friend bool operator <(const node &a, const node &b){
             11         return a.ti>b.ti;
             12     }
             13 };
             14 node f[MAXSIZE][MAXSIZE];
             15 char map[MAXSIZE][MAXSIZE];
             16 bool visited[MAXSIZE][MAXSIZE];
             17 bool getIt;
             18 int n,m,mins;
             19 int dir[4][2]={
             20     {1,0},
             21     {-1,0},
             22     {0,1},
             23     {0,-1}
             24 };
             25 
             26 void bfs(){
             27     node t,b;
             28     t.x=0;t.y=0;t.ti=0;
             29     priority_queue<node> Q;
             30     Q.push(t);
             31     visited[0][0]=true;
             32     while(!Q.empty()){
             33         b=Q.top();
             34         Q.pop();
             35         if(b.x==n-1&&b.y==m-1){
             36             getIt=true;
             37             mins=b.ti;
             38             return;
             39         }
             40         for(int k=0;k<4;k++){
             41             int i=b.x+dir[k][0];
             42             int j=b.y+dir[k][1];
             43             if(i<0||i>=n||j<0||j>=m)
             44                 continue;
             45             if(!visited[i][j]&&map[i][j]!='X'){
             46                 visited[i][j]=true;
             47                 f[i][j].x=b.x;f[i][j].y=b.y;f[i][j].ti=b.ti+1;//記錄前驅
             48                 if(map[i][j]=='.')
             49                     Q.push(node(i,j,b.ti+1));
             50                 else 
             51                     Q.push(node(i,j,b.ti+(map[i][j]-'0')+1));
             52             }
             53         }
             54     }
             55     puts("God please help our poor hero.");
             56 }
             57 inline void print(){
             58     stack<node> S;
             59     node temp=f[n-1][m-1];//終點的第一前繼點
             60     S.push(node(n-1,m-1,mins));//將終點放入
             61     while(temp.x!=0||temp.y!=0){//未到起點時
             62         S.push(temp);
             63         temp=f[temp.x][temp.y];
             64     }
             65     int k,t=1;
             66     if(map[0][0]!='.'){
             67         k=map[0][0]-'0';
             68         while(k--)
             69             printf("%ds:FIGHT AT (%d,%d)\n",t++,0,0);
             70     }
             71     while(!S.empty()){
             72         temp=S.top();
             73         S.pop();
             74         if(map[temp.x][temp.y]=='.')
             75             printf("%ds:(%d,%d)->(%d,%d)\n",t++,f[temp.x][temp.y].x,f[temp.x][temp.y].y,temp.x,temp.y);
             76         else {
             77             printf("%ds:(%d,%d)->(%d,%d)\n",t++,f[temp.x][temp.y].x,f[temp.x][temp.y].y,temp.x,temp.y);
             78             k=map[temp.x][temp.y]-'0';
             79             while(k--)
             80                 printf("%ds:FIGHT AT (%d,%d)\n",t++,temp.x,temp.y);
             81         }
             82     }
             83 }
             84 inline void scan(char &ch){
             85     while(ch=getchar())
             86         if(ch=='.'||ch=='X'||(ch>='1'&&ch<='9'))
             87             return ;
             88 }
             89 int main(){
             90     //freopen("in.txt","r",stdin);
             91     while(scanf("%d%d",&n,&m)!=EOF){
             92         for(int i=0;i<n;i++){
             93             for(int j=0;j<m;j++)
             94                 scan(map[i][j]);
             95         }
             96         if(map[0][0]=='X'||map[n-1][m-1]=='X'){
             97             puts("God please help our poor hero.");
             98             continue;
             99         }
            100         memset(visited,false,sizeof(visited));
            101         getIt=false;
            102         bfs();
            103         if(getIt){
            104             printf("It takes %d seconds to reach the target position, let me show you the way.\n",mins);
            105             print();
            106         } 
            107         puts("FINISH");
            108     }
            109     return 0;
            110 }
            posted on 2012-05-04 00:19 Leo.W 閱讀(337) 評論(0)  編輯 收藏 引用
            久久不见久久见免费视频7| 久久国产免费直播| 2021国内精品久久久久久影院| 久久久久99精品成人片三人毛片| 99久久99久久精品国产片| 91久久香蕉国产熟女线看| 性高湖久久久久久久久AAAAA| 久久人人爽人人人人片av| 国产精品99久久久精品无码| 久久精品无码一区二区无码 | 婷婷久久综合九色综合98| 久久精品综合一区二区三区| 武侠古典久久婷婷狼人伊人| 77777亚洲午夜久久多人| 久久国产精品-久久精品| 一日本道伊人久久综合影| 热re99久久6国产精品免费| 精品久久久久一区二区三区| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 99国内精品久久久久久久| 亚洲精品国产自在久久| 99久久国产热无码精品免费| 一本色道久久综合| 东京热TOKYO综合久久精品 | 国产午夜电影久久| 久久久久亚洲AV无码专区首JN | 国产叼嘿久久精品久久| 99久久无色码中文字幕人妻| 97精品伊人久久久大香线蕉| 无码人妻精品一区二区三区久久| 国产精品综合久久第一页| 无码国产69精品久久久久网站| 久久久精品国产Sm最大网站| 久久国产乱子伦免费精品| 少妇久久久久久被弄高潮| 色综合合久久天天给综看| 国产国产成人久久精品| 色综合色天天久久婷婷基地| 久久青青草原国产精品免费| 国内精品久久久久| 99久久99这里只有免费的精品|