洛古 P1312 Mayan游戏（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 }