hdu 1086

た入场券 2023-08-17 16:25 86阅读 0赞

1.纯dfs+结构体（记录位置x,y)-----超时

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/Aiahtwo/p/11300256.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/93f49166bf3a4b11bd9e9594391a8f72.png