POJ 3009

一个搜索的题目：

大意就是一个冰球，在冰面上滑动，你打击一次，就沿一个反向滑动，知道碰到墙就会停下，而墙则会破碎。

求从起点到终点的最短的击打次数。

题目中 2代表起点，3是终点，1是墙，0则是光滑的。

 1 #include <stdio.h>
 2 
 3 int h,w,a[25][25],step,xs,ys,xe,ye,steps;
 4 
 5 int dic[4][2]={-1,0,0,-1,1,0,0,1};
 6 void dfs(int x,int y)
 7 {
 8     if(step>10) return;    
 9     for(int i=0;i<4;i++)
10     {
11         int n=x+dic[i][0],m=y+dic[i][1];
12         int stop=0;
13         while(n<=h&&n>0&&m<=w&&m>0&&a[n][m]!=1)
14         {
15                 stop=1;
16                 if(n==xe&&m==ye)
17                     if(step<steps) steps=step;    //求最短的步数。
18                 n+=dic[i][0];
19                 m+=dic[i][1];
20         }
21         if(a[n][m]==1&&stop)
22         {
23             step++;
24             a[n][m]=0;
25             dfs(n-dic[i][0],m-dic[i][1]);     //回溯。
26             step--;
27             a[n][m]=1;
28         }
29     }
30 }
31 int main()
32 {
33     while(scanf("%d%d",&w,&h)&&w!=0&&h!=0)
34     {
35         for(int i=1;i<=h;i++)
36             for(int j=1;j<=w;j++)
37             {
38                 scanf("%d",&a[i][j]);
39                 if(a[i][j]==2) 
40                 {
41                     xs=i;
42                     ys=j;
43                 }
44                 if(a[i][j]==3)
45                 {
46                     xe=i;
47                     ye=j;
48                 }
49             }
50         steps=1000000;
51         step=1;
52         dfs(xs,ys);
53         if(steps<=10)printf("%d
",steps);
54         else printf("-1
");
55     }
56     return 0;
57 }