hdu 1175(BFS&DFS) 连连看

题目在这里:http://acm.hdu.edu.cn/showproblem.php?pid=1175

大家都很熟悉的连连看,原理基本就是这个,典型的搜索.这里用的是广搜.深搜的在下面

与普通的搜索比不同的是要求转折的线不能转折超过两次,就是在结构体中多开一个step(储存转折的次数)和一个dir(记录此刻的方向)

方向初始为-1,当行走一步后的方向与走之前不同的时候,step就应该加一,

然后还要注意的是为了保证得到的是所有的路线中转折次数最小的,这里的visit数组要用来保存每个点的最小转折次数,

所以初始化应该为很大

具体的看code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #include<climits>

 using namespace std;

 int map[][],visit[][];

 struct point {

     int x,y;

     int step,dir;//记录转折次数与方向

 } ;

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

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

 int n,m,ex,ey;

 int bfs(int sx,int sy)

 {

     int i;

     queue<point>Q;

     point next,now;

     now.x=sx;now.y=sy;

     now.step=;

     now.dir=-;

     Q.push(now);

     while (!Q.empty())

     {

         now=Q.front();

         Q.pop();

         if (now.x==ex&&now.y==ey)

             return ;

         for (i=;i<;i++)

         {

            next.x=now.x+dx[i];

            next.y=now.y+dy[i];

            next.step=now.step;

            next.dir=i;

            if (next.dir!=now.dir&&now.dir!=-)//方向发生变化就加一,但是是第一步的时候并不算是转折

                 next.step++;

            if ((next.x<=n&&next.x>=)&&(next.y<=m&&next.y>=)&&(map[next.x][next.y]==||(next.x==ex&&next.y==ey)))

            {

                if (next.step<)

                {

                    if (next.step<visit[next.x][next.y]) //让visit数组保存的是到每一点的最小转折次数

                    {

                        visit[next.x][next.y]=next.step;

                        Q.push(next);

                    }

                }

            }

         }

     }

     return ;

 }

 int main()

 {

     int i,j,t,sx,sy;

     while (~scanf("%d %d",&n,&m))

     {

         if (n==&&m==)

             break;

         for (i=;i<=n;i++){

             for (j=;j<=m;j++){

                 scanf("%d",&map[i][j]);

             }

         }

         scanf("%d",&t);

         while (t--)

         {

             cin>>sx>>sy>>ex>>ey;

             if (sx==ex&&sy==ey)

             {

                 printf("NO\n");

                 continue;

             }

             if (map[sx][sy]==||map[ex][ey]==||map[sx][sy]!=map[ex][ey])//这些特殊情况不要漏掉

             {

                 printf("NO\n");

                 continue;

             }

             for(i = ; i <= n; i++)

             for(j = ; j <= m; j++)

             visit[i][j] = ; //初始化为一个很大的数

             if (bfs(sx,sy)==)

                 printf("YES\n");

             else

                 printf("NO\n");

         }

     }

     return ;

 }

感觉这题深搜比广搜好想一些

无非就是多加了判断条件,注意回溯就行

code

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int map[][],visit[][];

 int n,m,ex,ey;

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

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

 int ans;

 void dfs(int fx,int fy,int dir,int step)

 {

     int x,y,i;

     if (ans==)return ;

     if (step>)return ;

     if (step==&&fx-ex!=&&fy-ey!=)return ;

     if (fx==ex&&fy==ey&&step<=)

     {

         ans=;

         return ;

     }

     for (i=;i<;i++)

     {

         x=fx+dx[i];

         y=fy+dy[i];

         if (y<=||y>m||x<=||x>n)continue;

         if (x==ex&&y==ey)

         ;

         else if (map[x][y]!=)

             continue;

         if (visit[x][y]!=)continue;

         //if (step>=3)continue;

         if (dir!=i&&dir!=-)

              step++;

         visit[x][y]=;

         dfs(x,y,i,step);

         visit[x][y]=;  //注意回溯,step也要回溯

         if (i!=dir&&dir!=-)

             step--;

     }

 }

 int main()

 {

     int i,t,j,sx,sy;

     while (~scanf("%d %d",&n,&m))

     {

         if (n==&&m==)

            break;

         for (i=;i<=n;i++)

         {

             for (j=;j<=m;j++)

                 scanf("%d",&map[i][j]);

         }

         scanf("%d",&t);

         while (t--)

         {

             memset(visit,,sizeof(visit));

             scanf("%d %d %d %d",&sx,&sy,&ex,&ey);

             if (sx==ex&&sy==ey)

             {

                 printf("NO\n");

                 continue;

             }

             if (map[sx][sy]!=map[ex][ey]||map[sx][sy]==||map[ex][ey]==)

             {

                 printf("NO\n");

                 continue;

             }

             ans=;

             visit[sx][sy]=;

             dfs(sx,sy,-,);

             if (ans==)

                printf("YES\n");

             else

                printf("NO\n");

         }

     }

     return ;

 }

巴特西

hdu 1175(BFS&DFS) 连连看

最新文章

热门文章