Problem 1753 Flip Game
原文：http://www.cppblog.com/NARUTOACM/archive/2010/04/26/100905.html
代码：
inline 内联函数的使用
在c++中，为了解决一些频繁调用的小函数大量消耗栈空间或者是叫栈内存的问题，特别的引入了inline修饰符，表示为内联函数。
可能说到这里，很多人还不明白什么是栈空间，其实栈空间就是指放置程序的局部数据也就是函数内数据的内存空间，在系统下，栈空间是有限的，如果频繁大量的使用就会造成因栈空间不足所造成的程序出错的问题，函数的死循环递归调用的最终结果就是导致栈内存空间枯竭。
#include <iostream>
#include <string>
using namespace std;
inline string dbtest(int a); //函数原形声明为inline即:内联函数
void main()
{
for (int i=1;i<=10;i++)
{
cout << i << ":" << dbtest(i) << endl;
}
cin.get();
}
string dbtest(int a)//这里不用再次inline,当然加上inline也是不会出错的
{
return (a%2>0)?"奇":"偶";
}
上面的例子就是标准的内联函数的用法，使用inline修饰带来的好处我们表面看不出来，其实在内部的工作就是在每个for循环的内部所有调用dbtest(i)的地方都换成了(i%2>0)?"奇":"偶"这样就避免了频繁调用函数对栈内存重复开辟所带来的消耗。
说到这里很多人可能会问，既然inline这么好，还不如把所谓的函数都声明成inline，嗯，这个问题是要注意的，inline的使用是有所限制的，inline只适合函数体内代码简单的函数使用，不能包含复杂的结构控制语句例如while switch，并且不能内联函数本身不能是直接递归函数(自己内部还调用自己的函数)。
说到这里我们不得不说一下在c语言中广泛被使用的#define语句，是的define的确也可以做到inline的这些工作，但是define是会产生副作用的，尤其是不同类型参数所导致的错误，由此可见inline有更强的约束性和能够让编译器检查出更多错误的特性，在c++中是不推荐使用define的
struct定义类
Description
Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:
- Choose any one of the 16 pieces.
- Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
Input
The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.
Output
Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).
Sample Input
bwwb
bbwb
bwwb
bwww
Sample Output
4
解题思路
题意：
一个棋盘，有黑白两种棋子。你可以翻动任一颗棋子，但是翻动有个规则，那就是该棋子周围的棋子都要跟着翻转，所谓翻转就是白变黑或黑变白。让你求出至少要翻转的次数使得棋盘达到一种状态，该状态就是棋盘中所有棋子都是同一种颜色。
思路：
此题我用的方法是状态压缩bfs，令白棋的状态为0，黑棋状态为1，显然要达到所要求的状态就只有两种情况：0000000000000000（2）=0（10）；1111111111111111（2）=65535（10）；因为有16个棋子，每个棋子一个状态，刚好可以用一个int型。此题我用此方法优化到16ms的极限了，不晓得还能如何优化，希望大牛帮忙看看。貌似此题还可以枚举做，这样做貌似很快，一般0ms，但我不晓得如何枚举，希望有大牛指点指点。源代码如下：
源程序
#include<iostream>
using namespace std;
struct node
{
int s;
int c;
};
class Queue
{
public:
node n[1<<17];
int front;
int rear;
static const int f=(1<<17)-1;
Queue()
{
front=rear=0;
}
void push(node x)
{
n[rear].s=x.s;
n[rear].c=x.c;
rear++;
rear&=f;
}
void pop(node &x)
{
x.s=n[front].s;
x.c=n[front].c;
front++;
front&=f;
}
};
Queue q;
int p[5][5];
int flag[1<<17];
void inline init()
{
int i,j;
for(i=1;i<=4;i++)
{
for(j=1;j<=4;j++)
p[i][j]=1<<(20-4*i-j);
}
}
int main()
{
init();
int s=0;
char a;
int i,j;
for(i=1;i<=4;i++)
{
for(j=1;j<=4;j++)
{
s=s<<1;
scanf("%c",&a);
if(a=='b')
s=s^1;
}
getchar();
}
node n,t;
n.s=s;
n.c=0;
q.push(n);
int f=0;
while(q.front!=q.rear)
{
q.pop(n);
if(n.s==0||n.s==65535)
{
f=1;
break;
}
for(i=1;i<=4;i++)
{
for(j=1;j<=4;j++)
{
int e=n.s;
e^=p[i][j];
if(i-1>0)
e^=p[i-1][j];
if(i+1<5)
e^=p[i+1][j];
if(j-1>0)
e^=p[i][j-1];
if(j+1<5)
e^=p[i][j+1];
t.s=e;
t.c=n.c+1;
if(!flag[e])
{
q.push(t);
flag[e]=1;
}
if(t.s==0||t.s==65535)
{
n.s=t.s;
n.c=t.c;
f=1;
break;
}
}
}
if(f==1)
break;
}
if(f==1)
printf("%d\n",n.c);
else
printf("Impossible\n");
return 0;
}