hdu 1175(BFS&DFS) 连连看

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

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

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

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

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

所以初始化应该为很大

具体的看code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 #include<climits>
 6 using namespace std;
 7 int map[1005][1005],visit[1005][1005];
 8 struct point {
 9     int x,y;
10     int step,dir;//记录转折次数与方向
11 } ;
12 int dx[4]={0,0,1,-1};
13 int dy[4]={1,-1,0,0};
14 int n,m,ex,ey;
15 int bfs(int sx,int sy)
16 {
17     int i;
18     queue<point>Q;
19     point next,now;
20     now.x=sx;now.y=sy;
21     now.step=0;
22     now.dir=-1;
23     Q.push(now);
24     while (!Q.empty())
25     {
26         now=Q.front();
27         Q.pop();
28         if (now.x==ex&&now.y==ey)
29             return 1;
30         for (i=0;i<4;i++)
31         {
32            next.x=now.x+dx[i];
33            next.y=now.y+dy[i];
34            next.step=now.step;
35            next.dir=i;
36            if (next.dir!=now.dir&&now.dir!=-1)//方向发生变化就加一,但是是第一步的时候并不算是转折
37                 next.step++;
38            if ((next.x<=n&&next.x>=1)&&(next.y<=m&&next.y>=1)&&(map[next.x][next.y]==0||(next.x==ex&&next.y==ey)))
39            {
40                if (next.step<3)
41                {
42                    if (next.step<visit[next.x][next.y]) //让visit数组保存的是到每一点的最小转折次数
43                    {
44                        visit[next.x][next.y]=next.step;
45                        Q.push(next);
46                    }
47                }
48            }
49         }
50     }
51     return 0;
52 }
53 int main()
54 {
55     int i,j,t,sx,sy;
56     while (~scanf("%d %d",&n,&m))
57     {
58         if (n==0&&m==0)
59             break;
60         for (i=1;i<=n;i++){
61             for (j=1;j<=m;j++){
62                 scanf("%d",&map[i][j]);
63             }
64         }
65         scanf("%d",&t);
66         while (t--)
67         {
68             cin>>sx>>sy>>ex>>ey;
69             if (sx==ex&&sy==ey)
70             {
71                 printf("NO
");
72                 continue;
73             }
74             if (map[sx][sy]==0||map[ex][ey]==0||map[sx][sy]!=map[ex][ey])//这些特殊情况不要漏掉
75             {
76                 printf("NO
");
77                 continue;
78             }
79             for(i = 1; i <= n; i++)
80             for(j = 1; j <= m; j++)
81             visit[i][j] = 10000; //初始化为一个很大的数
82             if (bfs(sx,sy)==1)
83                 printf("YES
");
84             else
85                 printf("NO
");
86         }
87 
88     }
89     return 0;
90 }

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

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

code

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int map[1011][1011],visit[1011][1011];
 5 int n,m,ex,ey;
 6 int dx[]={1,0,0,-1};
 7 int dy[]={0,1,-1,0};
 8 int ans;
 9 void dfs(int fx,int fy,int dir,int step)
10 {
11     int x,y,i;
12     if (ans==1)return ;
13     if (step>2)return ;
14     if (step==2&&fx-ex!=0&&fy-ey!=0)return ;
15     if (fx==ex&&fy==ey&&step<=2)
16     {
17         ans=1;
18         return ;
19     }
20     for (i=0;i<4;i++)
21     {
22         x=fx+dx[i];
23         y=fy+dy[i];
24         if (y<=0||y>m||x<=0||x>n)continue;
25         if (x==ex&&y==ey)
26         ;
27         else if (map[x][y]!=0)
28             continue;
29         if (visit[x][y]!=0)continue;
30         //if (step>=3)continue;
31         if (dir!=i&&dir!=-1)
32              step++;
33         visit[x][y]=1;
34         dfs(x,y,i,step);
35         visit[x][y]=0;  //注意回溯,step也要回溯
36         if (i!=dir&&dir!=-1)
37             step--;
38     }
39 }
40 int main()
41 {
42     int i,t,j,sx,sy;
43     while (~scanf("%d %d",&n,&m))
44     {
45         if (n==0&&m==0)
46            break;
47         for (i=1;i<=n;i++)
48         {
49             for (j=1;j<=m;j++)
50                 scanf("%d",&map[i][j]);
51         }
52         scanf("%d",&t);
53         while (t--)
54         {
55             memset(visit,0,sizeof(visit));
56             scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
57             if (sx==ex&&sy==ey)
58             {
59                 printf("NO
");
60                 continue;
61             }
62             if (map[sx][sy]!=map[ex][ey]||map[sx][sy]==0||map[ex][ey]==0)
63             {
64                 printf("NO
");
65                 continue;
66             }
67             ans=0;
68             visit[sx][sy]=1;
69             dfs(sx,sy,-1,0);
70 
71             if (ans==1)
72                printf("YES
");
73             else
74                printf("NO
");
75         }
76     }
77     return 0;
78 }