hdu 1086

  1 #include <iostream>
  2 #include <cstdio>
  3 #include<algorithm>
  4 #include <cstring>
  5 #include<cmath>
  6 using namespace std;
  7 #define ll long long
  8 #define maxn 100000
  9 int N,M;
 10 char s[105][105];
 11 char s1[105][105];
 12 struct node{
 13     int x;
 14     int y;
 15 };
 16 node f[110];
 17 node ans[110];
 18 int ans1,sum,ans2;
 19 int turn[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
 20 int flag=0;
 21 void dfs(int x,int y,int step)
 22 {
 23     if(x==N-1&&y==M-1)
 24     {
 25         sum=0;
 26         flag=1;
 27         for(int i=0;i<step;i++)
 28         {
 29             if(s1[f[i].x][f[i].y]==‘.‘)
 30             sum+=1;
 31             else
 32             {
 33                 int h=s1[f[i].x][f[i].y]-‘0‘;
 34                 sum+=h;
 35             }
 36         }
 37 
 38         ans2=step;
 39 
 40         if(sum<ans1)
 41         {
 42             ans1=sum;
 43             for(int i=0;i<step;i++)
 44             {
 45                 ans[i].x=f[i].x;
 46                 ans[i].y=f[i].y;
 47             }
 48         }
 49         return;
 50     }
 51     if(x<0||y<0||x>=N||y>=M)
 52         return;
 53 
 54     if(step>ans2&&ans2!=0)
 55         return;
 56 
 57     for(int i=0;i<4;i++)
 58     {
 59         int tx=x+turn[i][0];
 60         int ty=y+turn[i][1];
 61 
 62         if(s[tx][ty]!=‘X‘)
 63         {
 64             if(s[tx][ty]==‘.‘&&tx>=0&&tx<N&&ty>=0&&ty<M)
 65             {
 66                 s[tx][ty]=‘X‘;
 67                 f[step].x=tx;f[step].y=ty;
 68                 dfs(tx,ty,step+1);
 69                 s[tx][ty]=‘.‘;
 70             }
 71             if(s[tx][ty]!=‘.‘&&tx>=0&&tx<N&&ty>=0&&ty<M)
 72             {
 73                 s[tx][ty]=‘X‘;
 74                 int h=s[tx][ty]-‘0‘;
 75                f[step].x=tx;f[step].y=ty;
 76                dfs(tx,ty,step+1);
 77                s[tx][ty]=‘0‘+h;
 78             }
 79         }
 80     }
 81 
 82 }
 83 int main()
 84 {
 85     while(~scanf("%d%d",&N,&M))
 86     {
 87         getchar();
 88         for(int i=0;i<N;i++)
 89         {
 90             for(int j=0;j<M;j++)
 91                {
 92                     cin>>s[i][j];
 93                     s1[i][j]=s[i][j];
 94                }
 95             getchar();
 96         }
 97         f[0].x=0,f[0].y=0;
 98 
 99         ans1=maxn;
100         sum=1;
101         s[0][0]=‘X‘;
102         flag=0;
103         ans2=0;
104         dfs(0,0,1);
105 
106         if(flag==0)
107         {
108             printf("God please help our poor hero.\nFINISH\n");
109         }
110         else
111         {
112         if(s1[N-1][M-1]!=‘.‘)
113             ans1++;
114         printf("It takes %d seconds to reach the target position, let me show you the way.\n",ans1);
115         int yy=1;
116         for(int i=1;i<ans2;i++)
117         {
118              if(s1[ans[i].x][ans[i].y]==‘.‘)
119               {
120                   printf("%ds:(%d,%d)->(%d,%d)\n",yy,ans[i-1].x,ans[i-1].y,ans[i].x,ans[i].y);
121                   yy++;
122              }
123              else
124             {
125                 printf("%ds:(%d,%d)->(%d,%d)\n",yy,ans[i-1].x,ans[i-1].y,ans[i].x,ans[i].y);
126                 int j=s1[ans[i].x][ans[i].y]-‘0‘;
127                 yy++;
128                 for(int h=1;h<=j;h++)
129                 {
130                     printf("%ds:FIGHT AT (%d,%d)\n",yy,ans[i].x,ans[i].y);
131                     yy++;
132                 }
133             }
134         }
135         printf("FINISH\n");
136         }
137     }
138 }