Problem 1753 Flip Game
原文：http://m.shnenglu.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;
}