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，下一点就撞石头）。这思考一下就可以实现了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 void DFS(int x,int y,int di);

 const int N=,INF=0x3f3f3f3f;

 bool vis[N][N];

 int r,c,t,ex,ey,sx,sy,mx;

 int dx[]={,,,-};

 int dy[]={,-,,};

 bool isin(int x,int y)

 {

     return x>=&&x<r&&y>=&&y<c;

 }

 void DDFS(int a,int b,int x,int y,int d)

 {

     int i,j;

     if(t>) return ;

     i=x+a; j=y+b;

     if(!isin(i,j)) return ;

     if(!vis[i][j])

     {

         d=;

         if(i==ex&&j==ey)

         {

             mx=min(t,mx);

         }

         DDFS(a,b,i,j,d);

     }

     else if(vis[i][j]&&d)

     {

         vis[i][j]=;

         d=;

         t++;

         DFS(x,y,d);

         t--;

         vis[i][j]=;

     }

 }

 void DFS(int x,int y,int d)

 {

     for(int k=;k<;k++)

     {

         DDFS(dx[k],dy[k],x,y,d);

     }

 }

 int main()

 {

     //freopen("test.txt","r",stdin);

     while(scanf("%d%d",&c,&r)!=EOF&&c)

     {

         int x;

         for(int i=;i<r;i++){

             for(int j=;j<c;j++){

                 scanf("%d",&x);

                 if(x==)

                 {

                     ex=i;ey=j;

                     vis[i][j]=;

                 }

                 else if(x==)

                 {

                     sx=i;sy=j;

                     vis[i][j]=;

                 }

                 else vis[i][j]=x;

             }

         }

         t=;

         mx=INF;

         DFS(sx,sy,);

         if(mx==INF) printf("-1\n");

         else printf("%d\n",mx);

     }

     return ;

 }

　　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 深搜

最新文章

热门文章