Curling 2.0 POJ 3009(搜索)

原题

题目链接

题目分析

注意题目给的条件,石头到终点会终止.石头碰到冰块会停止,冰块消失.石头滑出边界,游戏失败.石头必须在10回合内到达终点否则游戏失败.按照这个条件写个dfs,记录一下深度就行了.

代码

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <utility>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <cstring>
 7 #include <string>
 8 #include <vector>
 9 #include <stack>
10 #include <queue>
11 #include <map>
12 #include <set> 
13 
14 using namespace std;
15 const int INF=0x3f3f3f3f; 
16 
17 int n,m;
18 int mapp[20][20];
19 int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
20 int ans;
21 
22 void dfs(int x,int y,int deep)
23 {
24 //    printf("now x=%d y=%d\n",x,y);
25     if(deep==10) return ;
26     for(int i=0;i<4;i++)
27     {
28         bool fault=false;
29         int nx=x+dx[i],ny=y+dy[i];
30         if(nx>=0&&nx<n&&ny>=0&&ny<m&&mapp[nx][ny]!=1)
31         {
32 //            printf("before nx=%d ny=%d\n",nx,ny);
33             while(mapp[nx][ny]!=1&&mapp[nx][ny]!=3) 
34             {
35                 nx+=dx[i],ny+=dy[i];
36                 if(nx<0||nx>=n||ny<0||ny>=m)
37                 {
38                     fault=true;
39                     break;
40                 }
41             }
42             if(fault) continue;
43 //            printf("after nx=%d ny=%d\n",nx,ny);
44             if(mapp[nx][ny]==3)
45             {
46                 if(!ans) ans=deep+1;
47                 else ans=min(ans,deep+1);
48             }
49             else
50             {
51                 mapp[nx][ny]=0;
52                 dfs(nx-dx[i],ny-dy[i],deep+1);
53                 mapp[nx][ny]=1;
54             }
55         }
56     }
57     return ;
58 }
59 
60 int main()
61 {
62 //    freopen("black.in","r",stdin);
63 //    freopen("black.out","w",stdout);
64     while(~scanf("%d %d",&m,&n)&&n&&m)
65     {
66         ans=0;
67         int x,y;
68         for(int i=0;i<n;i++)
69         for(int j=0;j<m;j++)
70         {
71             scanf("%d",&mapp[i][j]);
72             if(mapp[i][j]==2) x=i,y=j;
73         }
74         dfs(x,y,0);
75         if(ans) printf("%d\n",ans);
76         else printf("-1\n");
77     }
78     return 0;
79 }