首页 > 代码库 > poj3009 Curling 2.0 深搜

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)就可以沿着同一方向一直深入。

 

poj3009 Curling 2.0 深搜