POJ1681-画家问题
枚举的经典例题，枚举第一行即可，其余行唯一。
1 //画家问题，y表示黄色，w表示白色，怎样让墙上所有方格为y，操作类似熄灯问题poj1222 2 //memory 136K Time: 297 Ms 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 #define INF 0x3f3f3f3f 10 #define MAX 20 11 12 char m[MAX][MAX]; 13 int n,ans,sum; 14 int map[MAX][MAX],cpmap[MAX][MAX],p[MAX]; 15 int move[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; 16 17 void paint(int x,int y) 18 { 19 sum++; 20 cpmap[x][y] = !cpmap[x][y]; 21 for(int i=0;i<4;i++) 22 { 23 int tx = x+move[i][0]; 24 int ty = y+move[i][1]; 25 if(tx>=0 && tx<n && ty>=0 && ty<n) 26 cpmap[tx][ty] ^= 1; 27 } 28 } 29 30 /*尝试绘画*/ 31 int test_paint() 32 { 33 int i,j; 34 for(i=0;i<n;i++) //第一行 35 if(p[i]) 36 paint(0,i); 37 for(i=1;i<n;i++) //其余行唯一 38 { 39 for(j=0;j<n;j++) 40 { 41 if(!cpmap[i-1][j]) 42 paint(i,j); 43 } 44 } 45 //判断最后一行是否符合 46 int flag = 1; 47 for(i=0;i<n;i++) 48 if(!cpmap[n-1][i]) 49 { 50 flag = 0;break; 51 } 52 return flag; 53 } 54 55 int main() 56 { 57 int T; 58 int i,j; 59 scanf("%d",&T); 60 while(T--) 61 { 62 memset(p,0,sizeof(p)); 63 ans = INF; 64 scanf("%d",&n); 65 for(i=0;i<n;i++) 66 scanf("%s",m[i]); 67 //字符-转换为-0与1 68 for(i=0;i<n;i++) 69 for(j=0;j<n;j++) 70 if(m[i][j] == 'y') 71 map[i][j] = 1; 72 else 73 map[i][j] = 0; 74 75 p[0] = -1; 76 int res; 77 while(1) 78 { 79 sum = 0; 80 memcpy(cpmap,map,sizeof(map)); 81 /*二进制枚举第一行所有画法*/ 82 p[0]++; 83 res = p[0]/2; 84 j=1; 85 while(res) 86 { 87 p[j-1] = 0; 88 p[j]++; 89 res = p[j++]/2; 90 } 91 if(p[n]) 92 break; 93 if(test_paint()) 94 if(ans > sum) 95 ans = sum; 96 } 97 if(ans == INF) 98 printf("inf "); 99 else 100 printf("%d ",ans); 101 } 102 return 0; 103 }
POJ1166-拨钟问题
分析后枚举所有可能情况。
1 //暴力枚举-熄灯问题变形-拨钟问题，给出九个钟的时针位置(3,6,9,12)-(1,2,3,0)-将他们调到12点 即 2 //Memory 134K Time: 0 Ms 3 4 #include<iostream> 5 #include<cstring> 6 #include<cstdio> 7 using namespace std; 8 9 int sclock[10]; //source-clock 10 int pc[10]; //调好后时针位置 11 12 int main() 13 { 14 int j; 15 for (j = 1; j <= 9; j++) 16 scanf("%d",&sclock[j]); 17 int i[10]; //枚举所有九种拨法的情况-每种拨法最多3次 （第四次相当于没有拨动） 18 //4^9种情况 19 for (i[1] = 0; i[1] < 4; i[1]++) 20 for (i[2] = 0; i[2] < 4; i[2]++) 21 for (i[3] = 0; i[3] < 4; i[3]++) 22 for (i[4] = 0; i[4] < 4; i[4]++) 23 for (i[5] = 0; i[5] < 4; i[5]++) 24 for (i[6] = 0; i[6] < 4; i[6]++) 25 for (i[7] = 0; i[7] < 4; i[7]++) 26 for (i[8] = 0; i[8] < 4; i[8]++) 27 for (i[9] = 0; i[9] < 4; i[9]++) 28 { 29 pc[1] = (sclock[1] + i[1] + i[2] + i[4]) % 4; 30 pc[2] = (sclock[2] + i[1] + i[2] + i[3] + i[5]) % 4; 31 pc[3] = (sclock[3] + i[2] + i[3] + i[6]) % 4; 32 pc[4] = (sclock[4] + i[1] + i[4] + i[5] + i[7]) % 4; 33 pc[5] = (sclock[5] + i[1] + i[3] + i[5] + i[7] + i[9]) % 4; 34 pc[6] = (sclock[6] + i[3] + i[5] + i[6] + i[9]) % 4; 35 pc[7] = (sclock[7] + i[4] + i[7] + i[8]) % 4; 36 pc[8] = (sclock[8] + i[5] + i[7] + i[8] + i[9]) % 4; 37 pc[9] = (sclock[9] + i[6] + i[8] + i[9]) % 4; 38 39 int sum = 0; 40 for (j = 1; j <= 9; j++) 41 sum += pc[j]; 42 if (!sum) 43 { 44 for (j = 1; j <= 9;j++) 45 while (i[j]--) 46 printf("%d ",j); 47 printf(" "); 48 return 0; 49 } 50 } 51 return 0; 52 }
POJ1054-讨厌的青蛙
1 //Flog直线等步长踩稻子(array),找出踩过最多的一条Flog路径 2 //Memory 172K Time: 47 Ms 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<algorithm> 7 using namespace std; 8 9 #define min(x,y) ((x)>(y)?(y):(x)) 10 #define MAX 5005 11 12 struct Node { 13 int x, y; 14 }map[MAX]; //踩过路径 15 16 int row, col, length; 17 int n, maxlen = 2; 18 19 bool operator < (const Node &a, const Node &b) //重载全局运算符 <，以满足binary_search()与sort()处理Node的需要 20 { 21 //二重排序-行列序 22 if (a.x == b.x) return a.y < b.y; 23 return a.x < b.x; 24 } 25 26 /*延长路径-判定该路径是否成立*/ 27 void extend(Node second, int cx, int cy) 28 { 29 Node t; 30 t.x = second.x + cx; 31 t.y = second.y + cy; 32 while (t.x >= 1 && t.x <= row && t.y >= 1 && t.y <= col) 33 { 34 if (!binary_search(map, map + n, t))//没有find-不成立 35 { 36 length = 0; 37 break; 38 } 39 //find-成立 40 length++; 41 t.x += cx; 42 t.y += cy; 43 } 44 if (length > maxlen) 45 maxlen = length; 46 } 47 48 int main() 49 { 50 scanf("%d%d%d", &row, &col, &n); 51 for (int i = 0; i<n; i++) 52 scanf("%d%d", &map[i].x, &map[i].y); 53 54 sort(map, map + n); 55 for (int i = 0; i < n; i++) 56 for (int j = i + 1; j < n; j++) 57 { 58 length = 2; 59 int cx = map[j].x - map[i].x; //横步长 60 int cy = map[j].y - map[i].y; //纵步长 61 int px = map[i].x - cx; //(px,py)为假想跳跃起始位置 62 int py = map[i].y - cy; 63 64 if (px >= 1 && px <= row && py >= 1 && py <= col) 65 continue; //已访问此路径或路径不存在 66 67 px = map[i].x + (maxlen - 1)*cx; 68 py = map[i].y + (maxlen - 1)*cy; 69 if (px > row) break; //纵向须跳跃的最小距离超过row-遍历第一跳跃点 70 if (py > col || py < 1) continue; //横向须跳跃的最小距离超过col-遍历第二跳跃点 71 extend(map[j], cx, cy); //极值无误-尝试拓展 72 } 73 74 if (maxlen == 2) maxlen = 0; //没有最长路径 75 printf("%d ", maxlen); 76 return 0; 77 }