最近由于复习备考（然而考得还是很炸），很久没打题目了。现在开始刷寒假作业，不得不搞POJ
话说没有中文真的好烦啊！
先看1753
题目大意是说在一个4*4的格子中有黑白两色的棋子，你可以翻动其中的棋子但同时它四周（上下左右）的棋子也会被翻动，问你最少要翻几次才能翻成全黑或全白。
首先要想到，一个棋子翻转偶数次就相当于没翻，翻了奇数次就相当于翻了一次（很好想到），最重要的是它们翻转的顺序对答案并无影响！
所以一个棋子要么翻要么不翻，一共有2^（4*4）共65536种可能，直接爆搜即可。
注意一下翻棋子时不要越界
CODE
#include<cstdio>
#include<iostream>
using namespace std;
const int fx[]={,,,-,},fy[]={,,,,-};
char a[][];
int i,j,ans=;
inline bool check()
{
int w=,b=; char comp=a[][];
for (int i=;i<=;++i)
for (int j=;j<=;++j)
if (a[i][j]!=comp) return ;
return ;
}
inline void flip(int x,int y)
{
for (int i=;i<;++i)
{
int xx=x+fx[i],yy=y+fy[i];
if (xx<=||yy<=||xx>||yy>) continue;
if (a[xx][yy]=='w') a[xx][yy]='b'; else a[xx][yy]='w';
}
}
inline void DFS(int x,int y,int s)
{
if (check()) { ans=s<ans?s:ans; return; }
if (x>) return;
int xx=x,yy=y;
if (++yy>) ++xx,yy=;
flip(x,y);
DFS(xx,yy,s+);
flip(x,y);
DFS(xx,yy,s);
}
int main()
{
for (i=;i<=;++i)
for (j=;j<=;++j)
cin>>a[i][j];
DFS(,,);
if (ans!=) printf("%d",ans); else puts("Impossible");
return ;
}
2965其实是一道基本相似的题目，也是在4*4的方格中把所有的开关都翻成‘-‘，每次翻一个就会使它所在的那一行和那一列都翻转。
同样的做法，不过是开一个vector纪录一下答案而已。
CODE
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
vector <int> ans_x,ans_y;
char a[][];
int i,j,ans=;
bool f[][];
inline void copy()
{
for (int i=;i<=;++i)
for (int j=;j<=;++j)
if (f[i][j]) ans_x.push_back(i),ans_y.push_back(j);
}
inline bool check()
{
int w=,b=;
for (int i=;i<=;++i)
for (int j=;j<=;++j)
if (a[i][j]!='-') return ;
return ;
}
inline void flip(int x,int y)
{
for (int i=;i<=;++i)
if (a[i][y]=='-') a[i][y]='+'; else a[i][y]='-';
for (int j=;j<=;++j)
if (a[x][j]=='-') a[x][j]='+'; else a[x][j]='-';
if (a[x][y]=='-') a[x][y]='+'; else a[x][y]='-';
}
inline void DFS(int x,int y,int s)
{
if (check())
{
if (s<ans)
{
ans=s;
ans_x.clear(); ans_y.clear();
copy();
}
return;
}
if (x>) return;
int xx=x,yy=y;
if (++yy>) ++xx,yy=;
flip(x,y);
f[x][y]=;
DFS(xx,yy,s+);
flip(x,y);
f[x][y]=;
DFS(xx,yy,s);
}
int main()
{
for (i=;i<=;++i)
for (j=;j<=;++j)
cin>>a[i][j];
DFS(,,);
printf("%d\n",ans);
for (i=;i<ans;++i)
printf("%d %d\n",ans_x[i],ans_y[i]);
return ;
}