poj3009 Curling 2.0 深搜

PS：以前看到題目這么長就沒寫下去了。今天做了半天，沒做出來。準備看題解，打開了網站都忍住了，最后還是靠自己做出來的。算是一點進步吧。

分析：

　　題目的意思沒明白或者理解有偏差都沒辦法做題。看樣例3和樣例4，數據差不多的，但是一個輸出4，但是另外的一個卻是-1。再去看題目就會發現，題目的意思是在撞碎石頭之前必須走一個為值0的格子。我理解為需要加速。對樣例4，答案4是這樣出來的：初始位置為（1，3），第一步是到達（1，2），并且使得（1，1）點的值為0（撞碎了這里的石頭，0代表可以通行）；第二步是到達（1，3），并且是得（1，4）點的值為0；第三步是到達（1，4），并且使得（1，5）的值為0；第四步是到達（1，5），發現到達了終點，結束。樣例5也可以這樣得到。

　　樣例6錯誤的原因是因為超過了10步，這是題目的要求，超過10步就當不能到達處理。

　　這樣一來，可以知道了起點和終點的處理了。起點（終點）的坐標記錄下來，但是標記為0。

　　還有就是實現如何對一個方向進行搜索，以及如何標記在撞石頭之前已經走過0的位置（不能是這種情況：起點是0，下一點就撞石頭）。這思考一下就可以實現了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 void DFS(int x,int y,int di);
 8 const int N=22,INF=0x3f3f3f3f;
 9 bool vis[N][N];
10 int r,c,t,ex,ey,sx,sy,mx;
11 int dx[4]={0,0,1,-1};
12 int dy[4]={1,-1,0,0};
13 bool isin(int x,int y)
14 {
15     return x>=0&&x<r&&y>=0&&y<c;
16 }
17 void DDFS(int a,int b,int x,int y,int d)
18 {
19     int i,j;
20     if(t>10) return ;
21     i=x+a; j=y+b;
22     if(!isin(i,j)) return ;
23     if(!vis[i][j])
24     {
25         d=1;
26         if(i==ex&&j==ey)
27         {
28             mx=min(t,mx);
29         }
30         DDFS(a,b,i,j,d);
31     }
32     else if(vis[i][j]&&d)
33     {
34         vis[i][j]=0;
35         d=0;
36         t++;
37         DFS(x,y,d);
38         t--;
39         vis[i][j]=1;
40     }
41 }
42 void DFS(int x,int y,int d)
43 {
44 
45     for(int k=0;k<4;k++)
46     {
47         DDFS(dx[k],dy[k],x,y,d);
48     }
49 }
50 int main()
51 {
52     //freopen("test.txt","r",stdin);
53     while(scanf("%d%d",&c,&r)!=EOF&&c)
54     {
55         int x;
56         for(int i=0;i<r;i++){
57             for(int j=0;j<c;j++){
58                 scanf("%d",&x);
59                 if(x==3)
60                 {
61                     ex=i;ey=j;
62                     vis[i][j]=0;
63                 }
64                 else if(x==2)
65                 {
66                     sx=i;sy=j;
67                     vis[i][j]=0;
68                 }
69                 else vis[i][j]=x;
70             }
71         }
72         t=1;
73         mx=INF;
74         DFS(sx,sy,0);
75         if(mx==INF) printf("-1\n");
76         else printf("%d\n",mx);
77     }
78     return 0;
79 }

View Code

　　DFS(x,y,d) ： (x,y)是起點的坐標，d是標記是否有經過被標記0的點。1表示經過了，0表示沒有。

　　DDFS(a,b,x,y,d) ：(a,b)是方向向量，表明向什么方向搜索；x,y,d同上。

　　通過d的記錄就可以知道石頭可不可以撞碎。使用(a,b)就可以沿著同一方向一直深入。

轉載于:https://www.cnblogs.com/Potato-lover/p/4114002.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/273507.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/273507.shtml
英文地址，請注明出處：http://en.pswp.cn/news/273507.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！