洛谷P1274-魔术数字游戏

Problem 洛谷P1274-魔术数字游戏

Accept: 118 Submit: 243
Time Limit: 1000 mSec Memory Limit : 128MB

Problem Description

填数字方格的游戏有很多种变化，如下图所示的4×4方格中，我们要选择从数字1到16来填满这十六个格子(Aij，其中i＝1..4，j＝1..4)。为了让游戏更有挑战性，我们要求下列六项中的每一项所指定的四个格子，其数字累加的和必须为34：

四个角落上的数字，即A11+A14+A41+A44＝34。

每个角落上的2×2方格中的数字，例如左上角：A11+A12+A21+A22＝34。

最中间的2×2方格中的数字，即A22+A23+A32+A33=34。

每条水平线上四个格子中的数字，即Ai1+Ai2+Ai3+Ai4＝34，其中i＝1..4。

每条垂直线上四个格子中的数字，即A1j+A2j+A3j+A4j＝34，其中j＝1..4。

两条对角线上四个格子中的数字，例如左上角到右下角：A11+A22+A33+A44＝34。

右上角到左下角：A14+A23+A32+A41＝34

Input

输入文件会指定把数字1先固定在某一格内。输入的文件只有一行包含两个正数据I和J，表示第1行和第J列的格子放数字1。剩下的十五个格子，请按照前述六项条件用数字2到16来填满。

Output

把全部的正确解答用每4行一组写到输出文件，每行四个数，相邻两数之间用一个空格隔开。两组答案之间，要以一个空白行相间，并且依序排好。排序的方式，是先从第一行的数字开始比较，每一行数字，由最左边的数字开始比，数字较小的解答必须先输出到文件中。

Sample Input

1 1

Sample output

1 4 13 16
14 15 2 3
8 5 12 9
11 10 7 6

1 4 13 16
14 15 2 3
12 9 8 5
7 6 11 10

题目链接：https://www.luogu.org/problemnew/show/P1274

题解：无脑爆搜就好，剪枝的话就按照题目说的剪，代码比较冗长

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 using namespace std;
  6 
  7 const int maxn = 6;
  8 
  9 int gra[maxn][maxn];
 10 bool used[maxn*3];
 11 
 12 void output(){
 13     for(int i = 1;i <= 4;i++){
 14         printf("%d",gra[i][1]);
 15         for(int j = 2;j <= 4;j++){
 16             printf(" %d",gra[i][j]);
 17         }
 18         printf("
");
 19     }
 20     printf("
");
 21 }
 22 
 23 void dfs(int x,int y){
 24     if(x > 4){
 25         output();
 26         return;
 27     }
 28     if(gra[x][y] == 1){
 29         if(x==2 && y==2){
 30             if(gra[1][1]+gra[1][2]+gra[2][1]+gra[2][2] != 34) return;
 31         }
 32         if(x==2 && y==4){
 33             if(gra[1][3]+gra[1][4]+gra[2][3]+gra[2][4] != 34) return;
 34         }
 35         if(x==4 && y==2){
 36             if(gra[3][1]+gra[3][2]+gra[4][1]+gra[4][2] != 34) return;
 37         }
 38         if(x==4 && y==4){
 39             if(gra[3][3]+gra[3][4]+gra[4][3]+gra[4][4] != 34) return;
 40             if(gra[1][1]+gra[2][2]+gra[3][3]+gra[4][4] != 34) return;
 41             if(gra[1][1]+gra[1][4]+gra[4][1]+gra[4][4] != 34) return;
 42         }
 43         if(x==4 && y==1){
 44             if(gra[1][4]+gra[4][1]+gra[2][3]+gra[3][2] != 34) return;
 45         }
 46         if(x==3 && y==3){
 47             if(gra[2][2]+gra[2][3]+gra[3][2]+gra[3][3] != 34) return;
 48         }
 49         if(x == 4){
 50             if(gra[1][y]+gra[2][y]+gra[3][y]+gra[4][y] != 34) return;
 51         }
 52         if(y == 4){
 53             if(gra[x][1]+gra[x][2]+gra[x][3]+gra[x][4] != 34) return;
 54         }
 55         if(y == 4) dfs(x+1,1);
 56         else dfs(x,y+1);
 57     }
 58     else{
 59         for(int i = 2;i <= 16;i++){
 60             if(!used[i]){
 61                 //output();
 62                 gra[x][y] = i;
 63                 if(x==2 && y==2){
 64                     if(gra[1][1]+gra[1][2]+gra[2][1]+gra[2][2] != 34){
 65                         gra[x][y] = 0;
 66                         continue;
 67                     }
 68                 }
 69                 if(x==2 && y==4){
 70                     if(gra[1][3]+gra[1][4]+gra[2][3]+gra[2][4] != 34){
 71                         gra[x][y] = 0;
 72                         continue;
 73                     }
 74                 }
 75                 if(x==4 && y==2){
 76                     if(gra[3][1]+gra[3][2]+gra[4][1]+gra[4][2] != 34){
 77                         continue;
 78                         gra[x][y] = 0;
 79                     }
 80                 }
 81                 if(x==4 && y==4){
 82                     if(gra[3][3]+gra[3][4]+gra[4][3]+gra[4][4] != 34){
 83                         gra[x][y] = 0;
 84                         continue;
 85                     }
 86                     if(gra[1][1]+gra[2][2]+gra[3][3]+gra[4][4] != 34){
 87                         gra[x][y] = 0;
 88                         continue;
 89                     }
 90                     if(gra[1][1]+gra[1][4]+gra[4][1]+gra[4][4] != 34){
 91                         gra[x][y] = 0;
 92                         continue;
 93                     }
 94                 }
 95                 if(x==4 && y==1){
 96                     if(gra[1][4]+gra[4][1]+gra[2][3]+gra[3][2] != 34){
 97                         gra[x][y] = 0;
 98                         continue;
 99                     }
100                 }
101                 if(x == 3 && y==3){
102                     if(gra[2][2]+gra[2][3]+gra[3][2]+gra[3][3] != 34){
103                         gra[x][y] = 0;
104                         continue;
105                     }
106                 }
107                 if(x == 4){
108                     if(gra[1][y]+gra[2][y]+gra[3][y]+gra[4][y] != 34){
109                         gra[x][y] = 0;
110                         continue;
111                     }
112                 }
113                 if(y == 4){
114                     if(gra[x][1]+gra[x][2]+gra[x][3]+gra[x][4] != 34){
115                         gra[x][y] = 0;
116                         continue;
117                     }
118                 }
119                 used[i] = true;
120                 if(y == 4) dfs(x+1,1);
121                 else dfs(x,y+1);
122                 used[i] = false;
123                 gra[x][y] = 0;
124             }
125         }
126     }
127 }
128 
129 int main()
130 {
131     //freopen("input.txt","r",stdin);
132     int x,y;
133     scanf("%d%d",&x,&y);
134     memset(gra,0,sizeof(gra));
135     memset(used,false,sizeof(used));
136     gra[x][y] = 1;
137     used[1] = true;
138     dfs(1,1);
139     return 0;
140 }