POJ1681-画家问题
枚举的经典例题，枚举第一行即可，其余行唯一。
//画家问题，y表示黄色，w表示白色，怎样让墙上所有方格为y，操作类似熄灯问题poj1222
//memory 136K Time: 297 Ms
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std; #define INF 0x3f3f3f3f
#define MAX 20 char m[MAX][MAX];
int n,ans,sum;
int map[MAX][MAX],cpmap[MAX][MAX],p[MAX];
int move[][] = {{,},{-,},{,},{,-}}; void paint(int x,int y)
{
sum++;
cpmap[x][y] = !cpmap[x][y];
for(int i=;i<;i++)
{
int tx = x+move[i][];
int ty = y+move[i][];
if(tx>= && tx<n && ty>= && ty<n)
cpmap[tx][ty] ^= ;
}
} /*尝试绘画*/
int test_paint()
{
int i,j;
for(i=;i<n;i++) //第一行
if(p[i])
paint(,i);
for(i=;i<n;i++) //其余行唯一
{
for(j=;j<n;j++)
{
if(!cpmap[i-][j])
paint(i,j);
}
}
//判断最后一行是否符合
int flag = ;
for(i=;i<n;i++)
if(!cpmap[n-][i])
{
flag = ;break;
}
return flag;
} int main()
{
int T;
int i,j;
scanf("%d",&T);
while(T--)
{
memset(p,,sizeof(p));
ans = INF;
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%s",m[i]);
//字符-转换为-0与1
for(i=;i<n;i++)
for(j=;j<n;j++)
if(m[i][j] == 'y')
map[i][j] = ;
else
map[i][j] = ; p[] = -;
int res;
while()
{
sum = ;
memcpy(cpmap,map,sizeof(map));
/*二进制枚举第一行所有画法*/
p[]++;
res = p[]/;
j=;
while(res)
{
p[j-] = ;
p[j]++;
res = p[j++]/;
}
if(p[n])
break;
if(test_paint())
if(ans > sum)
ans = sum;
}
if(ans == INF)
printf("inf\n");
else
printf("%d\n",ans);
}
return ;
}
POJ1166-拨钟问题
分析后枚举所有可能情况。
//暴力枚举-熄灯问题变形-拨钟问题，给出九个钟的时针位置(3,6,9,12)-(1,2,3,0)-将他们调到12点 即
//Memory 134K Time: 0 Ms #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; int sclock[]; //source-clock
int pc[]; //调好后时针位置 int main()
{
int j;
for (j = ; j <= ; j++)
scanf("%d",&sclock[j]);
int i[]; //枚举所有九种拨法的情况-每种拨法最多3次 （第四次相当于没有拨动）
//4^9种情况
for (i[] = ; i[] < ; i[]++)
for (i[] = ; i[] < ; i[]++)
for (i[] = ; i[] < ; i[]++)
for (i[] = ; i[] < ; i[]++)
for (i[] = ; i[] < ; i[]++)
for (i[] = ; i[] < ; i[]++)
for (i[] = ; i[] < ; i[]++)
for (i[] = ; i[] < ; i[]++)
for (i[] = ; i[] < ; i[]++)
{
pc[] = (sclock[] + i[] + i[] + i[]) % ;
pc[] = (sclock[] + i[] + i[] + i[] + i[]) % ;
pc[] = (sclock[] + i[] + i[] + i[]) % ;
pc[] = (sclock[] + i[] + i[] + i[] + i[]) % ;
pc[] = (sclock[] + i[] + i[] + i[] + i[] + i[]) % ;
pc[] = (sclock[] + i[] + i[] + i[] + i[]) % ;
pc[] = (sclock[] + i[] + i[] + i[]) % ;
pc[] = (sclock[] + i[] + i[] + i[] + i[]) % ;
pc[] = (sclock[] + i[] + i[] + i[]) % ; int sum = ;
for (j = ; j <= ; j++)
sum += pc[j];
if (!sum)
{
for (j = ; j <= ;j++)
while (i[j]--)
printf("%d ",j);
printf("\n");
return ;
}
}
return ;
}
POJ1054-讨厌的青蛙
//Flog直线等步长踩稻子(array),找出踩过最多的一条Flog路径
//Memory 172K Time: 47 Ms
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; #define min(x,y) ((x)>(y)?(y):(x))
#define MAX 5005 struct Node {
int x, y;
}map[MAX]; //踩过路径 int row, col, length;
int n, maxlen = ; bool operator < (const Node &a, const Node &b) //重载全局运算符 <，以满足binary_search()与sort()处理Node的需要
{
//二重排序-行列序
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
} /*延长路径-判定该路径是否成立*/
void extend(Node second, int cx, int cy)
{
Node t;
t.x = second.x + cx;
t.y = second.y + cy;
while (t.x >= && t.x <= row && t.y >= && t.y <= col)
{
if (!binary_search(map, map + n, t))//没有find-不成立
{
length = ;
break;
}
//find-成立
length++;
t.x += cx;
t.y += cy;
}
if (length > maxlen)
maxlen = length;
} int main()
{
scanf("%d%d%d", &row, &col, &n);
for (int i = ; i<n; i++)
scanf("%d%d", &map[i].x, &map[i].y); sort(map, map + n);
for (int i = ; i < n; i++)
for (int j = i + ; j < n; j++)
{
length = ;
int cx = map[j].x - map[i].x; //横步长
int cy = map[j].y - map[i].y; //纵步长
int px = map[i].x - cx; //(px,py)为假想跳跃起始位置
int py = map[i].y - cy; if (px >= && px <= row && py >= && py <= col)
continue; //已访问此路径或路径不存在 px = map[i].x + (maxlen - )*cx;
py = map[i].y + (maxlen - )*cy;
if (px > row) break; //纵向须跳跃的最小距离超过row-遍历第一跳跃点
if (py > col || py < ) continue; //横向须跳跃的最小距离超过col-遍历第二跳跃点
extend(map[j], cx, cy); //极值无误-尝试拓展
} if (maxlen == ) maxlen = ; //没有最长路径
printf("%d\n", maxlen);
return ;
}