HDOJ 1026 dfs路径保存

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 int g[101][101];
 5 #define inf 0xffffff
 6 int n,m;
 7 int min;
 8 int sx[4]={0,1,0,-1};
 9 int sy[4]={1,0,-1,0};
10 int que[1001][2];
11 int front,rear;
12 void dfs(int x,int y,int c_step)
13 {
14     if(x==n&&y==m)
15     {
16         if(c_step<min)
17         {min=c_step;return;}
18     }
19     if(abs(x-n)+abs(y-m)+c_step>n*m-1)return;
20     for(int i=0;i<4;i++)
21     {
22         int xx,yy;
23         xx=x+sx[i];
24         yy=y+sy[i];
25         if(xx<=n&&xx>=1&&yy<=m&&yy>=1&&g[xx][yy]!=-1)
26         {
27             int zhi=g[xx][yy];
28             g[xx][yy]=-1;
29             dfs(xx,yy,c_step+zhi+1);
30             g[xx][yy]=zhi;
31         }
32         
33     }
34 
35 
36 }
37 int main()
38 {
39     char c;
40     int i,j;
41     while(scanf("%d %d",&n,&m)!=EOF)
42     {
43         getchar();
44         for(i=1;i<=n;i++)
45         {
46             for(j=1;j<=m;j++)
47             {
48                 c=getchar();
49                 if(c=='.')
50                     g[i][j]=0;
51                 else if(c=='#')
52                     g[i][j]=-1;
53                 else 
54                     g[i][j]=c-'0';
55             }
56             getchar();
57         }
58         min=inf;
59         int start=g[1][1];
60         dfs(1,1,start);
61         printf("
");
62         if(min>n*m-1)
63             printf("God please help our poor hero.
");
64         else
65             printf("It takes %d seconds to reach the target position, let me show you the way.
",min);
66         printf("FINISH
");
67     }
68     return 0;
69 }
View Code