首页 > 代码库 > poj 1069 DFS+剪枝
poj 1069 DFS+剪枝
1 /* 2 题意:给出一个边长为S的六边形,再给出n种边长不同的三角形,所有的长度均为整型,问这n种三角形是否 3 能够拼成这个六边形。 4 5 题解:DFS+剪枝 6 这题的关键是图的表示方法以及剪枝,图我用了一个二维数组直接表示: 7 111111111111111111111 8 111110000000000011111 9 111100000000000001111 10 111000000000000000111 11 110000000000000000011 12 100000000000000000001 13 100000000000000000001 14 110000000000000000011 15 111000000000000000111 16 111100000000000001111 17 111110000000000011111 18 111111111111111111111 19 然后就是DFS,自上而下,从左往右,对每个最小的三角形进行搜索,按照顺序遍历能使得搜索的数量会少一 20 点,每一次对当前位置判断并将正三角形和倒三角形分别加入尝试; 21 剪枝: 22 大于S的三角形忽略,取模为0的两个三角形只需选边较短的,从短边的三角形开始尝试,如果某个三角形边长 23 能够整除S,那么该三角形可以直接组成六边形 24 */ 25 #include <cstdio> 26 #include <cstring> 27 #include <algorithm> 28 29 using namespace std; 30 31 int stype[15]; 32 int S,n; 33 bool gra[105][105]; 34 35 bool dfs(int x, int y) 36 { 37 for(int i=0; i<=2*S+1; i++) 38 { 39 for(int j=0; j<=4*S; j++) 40 printf("%d",gra[i][j]); 41 printf("\n"); 42 } 43 if (x > 2*S) 44 return true; 45 46 // 判断是否在图上 47 if (x <= S && y > 3*S+x-1) 48 return dfs(x+1,S-x); 49 if (x > S && y > 4*S-1-(x-S-1)) 50 return dfs(x+1,x+1-S); 51 if (gra[x][y]) // 超过图上则换行 52 return dfs(x,y+1); 53 54 if (((x+y)&1) != ((1+S)&1)) // 三角形底在上 55 { 56 for(int i=0; i<n; i++) 57 { 58 bool flag = true; 59 for(int j=0; j<2*stype[i]-1; j++) 60 if (gra[x][y+j]) 61 { 62 flag = false; 63 break; 64 } 65 if (flag) 66 { 67 for(int j=0; j<stype[i]; j++) 68 if (gra[x+j][y+j] || gra[x+j][y+2*stype[i]-2-j]) 69 { 70 flag = false; 71 break; 72 } 73 } 74 if (flag) // 可以访问 75 { 76 for(int j=0; j<stype[i]; j++) 77 for(int k=0; k<2*stype[i]-1-2*j;k++) 78 gra[x+j][y+j+k] = true; 79 if (!dfs(x,y+1)) 80 for(int j=0; j<stype[i]; j++) 81 for(int k=0; k<2*stype[i]-1-2*j;k++) 82 gra[x+j][y+j+k] = false; 83 else 84 return true; 85 } 86 } 87 } 88 else // 底在下 89 { 90 for(int i=0; i<n; i++) 91 { 92 bool flag = true; 93 for(int j=0; j<stype[i]; j++) 94 { 95 if (gra[x+j][y+j] || gra[x+j][y-j]) 96 { 97 flag = false; 98 break; 99 } 100 } 101 if (flag) 102 { 103 for(int j=0; j<stype[i]; j++) 104 for(int k=0; k<j+1; k++) 105 gra[x+j][y+k] = gra[x+j][y-k] = true; 106 if (!dfs(x,y+1)) 107 for(int j=0; j<stype[i]; j++) 108 for(int k=0; k<j+1; k++) 109 gra[x+j][y+k] = gra[x+j][y-k] = false; 110 else 111 return true; 112 } 113 } 114 } 115 return false; 116 } 117 118 int main(void) 119 { 120 int t; 121 scanf("%d",&t); 122 123 while (t--) 124 { 125 scanf("%d%d",&S,&n); 126 for(int i=0; i<n; i++) 127 scanf("%d",&stype[i]); 128 memset(gra,false,sizeof(gra)); 129 130 for(int i=0; i<=4*S; i++) 131 gra[0][i] = gra[i][0] = gra[2*S+1][i] = gra[i][4*S] = true; 132 133 for(int i=1; i<=S-1; i++) 134 for(int j=1; j<=i; j++) 135 gra[S-i][j] = gra[S-i][4*S-1-(j-1)] = gra[S+1+i][j] = gra[S+1+i][4*S-1-(j-1)] = true; 136 137 sort(stype,stype+n); 138 139 bool tflag = false; 140 for(int i=0; i<n; i++) 141 { 142 if (S % stype[i] == 0) 143 { 144 printf("YES\n"); 145 tflag = true; 146 break; 147 } 148 } 149 for(int i=0; i<n; i++) 150 { 151 if (stype[i] > S) 152 { 153 n = i; 154 break; 155 } 156 } 157 158 for(int i=0; i<n-1; i++) 159 { 160 for(int j=i+1; j<n; j++) 161 { 162 if (stype[j] % stype[i] == 0) 163 { 164 for(int k=j+1; k<n; k++) 165 stype[k-1] = stype[k]; 166 n--; 167 j--; 168 } 169 } 170 } 171 172 if (tflag) 173 continue; 174 175 if (dfs(1,S)) 176 printf("YES\n"); 177 else 178 printf("NO\n"); 179 } 180 return 0; 181 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。