亲宝软件园·资讯

展开

洛古 P1312 Mayan游戏(dfs+剪枝)

橙剑oo 人气:0

题目链接

这道题和俄罗斯方块很像

很明显,我们可以看出这是一个dfs,但是,我们需要几条剪枝:

1.如果只剩下1个或2个同样颜色的方块,那么直接退出

2.相同的块不用交换

3.注意优先性,优先左边换右边

但是这题就这么样就完了吗

显然,并没有这么简单:剪枝清楚了,你确定就能写出来吗(这是我写过最长的dfs)

接下来讲一下我的程序架构:

init函数:输入,存储数据

fall函数:模拟方块下落

printans函数:输出答案

clear函数:清除棋盘

isempty函数:判断是否为空

judge函数:剪枝1

dfs函数:搜索

下面是代码,看不懂上面的话,代码里也有注释

 

 

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int N = 5;
  5 const int M = 7;
  6 
  7 int maxstep, chess[N][M];
  8 int cnt[11];
  9 int answer[5][3];
 10 
 11 void init()
 12 {
 13     cin>>maxstep;
 14     for(int i=0; i<N; i++)
 15     {
 16         int j=0,x;
 17         cin>>x;
 18         while(x!=0)
 19         {
 20             chess[i][j]=x;
 21             j++;
 22             cin>>x;
 23         }
 24     }
 25 }
 26 
 27 void fall()    //清除后方块下落
 28 {
 29     for(int i=0; i<N; i++)
 30         for(int j=0; j<M; j++)
 31         {
 32             if(chess[i][j]!=0)
 33                 continue;
 34             int k;
 35             for(k=j+1; k<M; k++)
 36                 if(chess[i][k]!=0)
 37                 {
 38                     swap(chess[i][j],chess[i][k]);
 39                     break;
 40                 }
 41             if(k==M)
 42                 break;
 43         }
 44 }
 45 
 46 void printans()     //输出
 47 {
 48     for(int i=0; i<maxstep; i++)
 49         printf("%d %d %d\n",answer[i][0],answer[i][1],answer[i][2]);
 50     return;
 51 }
 52 
 53 bool clear()        //清除棋盘
 54 {
 55     bool empty[N][M];
 56     memset(empty,false,sizeof(empty));
 57     for(int i=0; i<N-2; i++)
 58         for(int j=0; j<M; j++)
 59             if(chess[i][j]!=0 && chess[i][j]==chess[i+1][j] 
 60                 && chess[i+1][j]==chess[i+2][j]) {
 61                     empty[i][j]=empty[i+1][j]=empty[i+2][j]=true;
 62                 }
 63                 
 64 
 65     for(int i=0; i<N; i++)
 66         for(int j=0; j<M-2; j++)
 67             if(chess[i][j]!=0 && chess[i][j]==chess[i][j+1]
 68                 && chess[i][j+1]==chess[i][j+2]) {
 69                     empty[i][j]=empty[i][j+1]=empty[i][j+2]=true;
 70                 }
 71 
 72     bool res=false;
 73     for(int i=0; i<N; i++)
 74         for(int j=0; j<M; j++)
 75             if(empty[i][j])
 76             {
 77                 chess[i][j]=0;
 78                 res=true;
 79             }
 80     return res;
 81 }
 82 
 83 bool isempty()      // 判断棋盘是否为空
 84 {
 85     for(int i=0; i<N; i++)
 86         for(int j=0; j<M; j++)
 87             if(chess[i][j]!=0)
 88                 return false;
 89     return true;
 90 }
 91 
 92 bool judge()        //判断是否有一种颜色的块数量为1或2
 93 {
 94     memset(cnt,0,sizeof(cnt));
 95     for(int i=0; i<N; i++)
 96         for(int j=0; j<M; j++)
 97             cnt[chess[i][j]]++;
 98     for(int i=1; i<=10; i++)
 99         if(cnt[i]==1||cnt[i]==2)
100             return false;
101     return true;
102 }
103 
104 bool dfs(int step)      //搜索
105 {
106     if(isempty())       //发现一组解
107     {
108         printans();
109         return true;
110     }
111     if(step>=maxstep || !judge())     //剪枝与结束条件
112         return false; 
113 
114     int now[N][M];      // 记录当前状态,回溯时候用 
115     for(int i=0; i<N; i++)      //复制棋盘
116         for(int j=0; j<M; j++)
117             now[i][j]=chess[i][j];
118 
119     for(int i=0; i<N; i++)
120         for(int j=0; j<M; j++)      //枚举每一个方块
121         {
122             //右移
123             if(i!=N-1 && chess[i][j]!=0 && chess[i][j]!=chess[i+1][j])
124             {
125                 swap(chess[i][j], chess[i+1][j]);
126                 answer[step][0]=i;
127                 answer[step][1]=j;
128                 answer[step][2]=1;
129                 fall();
130                 while(clear())
131                     fall();
132                 if(dfs(step+1))
133                     return true;
134             }
135 
136             for(int k1=0; k1<N; k1++)
137                 for(int k2=0; k2<M; k2++)
138                     chess[k1][k2]=now[k1][k2];
139 
140             //左移
141             if(i!=0 && chess[i][j]!=0 && chess[i-1][j]==0)
142             {
143                 swap(chess[i][j], chess[i-1][j]);
144                 answer[step][0]=i;
145                 answer[step][1]=j;
146                 answer[step][2]=-1;
147                 fall();
148                 while(clear())
149                     fall();
150                 if(dfs(step+1))
151                     return true;
152             }
153 
154             for(int k1=0; k1<N; k1++)
155                 for(int k2=0; k2<M; k2++)
156                     chess[k1][k2]=now[k1][k2];
157         }
158     return false;
159 }
160 
161 /*
162 搜索+剪枝 
163 剪枝原则:
164 1,交换两个相同颜色的块没有意义。
165 2,如果一种颜色的块数量为1或2,则当前局面无解。
166 3,因为要求字典序最小的解,所以一个块仅当左边为空时尝试左移
167 (若左面有方块,那么在搜i-1列时将其右移,和在i列时左移是等效的,故可以剪枝) 
168 */ 
169 int main()
170 {
171     ios::sync_with_stdio(false);
172     cin.tie(0);
173     
174     init();
175     if(!dfs(0))
176         cout<<-1<<endl;
177     return 0;
178 }

 

补充:说到俄罗斯方块,我又想起来USACO的这道题,有兴趣的同学可以去做做

 

加载全部内容

相关教程
猜你喜欢
用户评论