今天天氣很好！
首先題意是這樣的：：
翻蓋游戲是在一個長方形的4x4場上進行的，其16個方格中的每一個都放置了雙面的棋子，每一塊的一邊是白色的，另一邊是黑色的，每一塊都是躺著的，要么是黑色的，要么是白色的，每一輪你翻轉3到5塊，從而改變他們的上邊的顏色從黑色到白色，反之亦然，每一輪將翻轉的棋子按照以下規則進行選擇：
- 選擇16件中的任何一件，
- 將選定的部分和所有相鄰的部分翻轉到左邊、右邊、頂部和所選部分的底部(如果有的話)，
- 以以下立場為例：
bwbw
瓦特
bbwb
bwwb
在這里，“b”表示其黑色一側向上的部分，而“w”表示其白色一側向上的部分，如果我們選擇從第3行翻轉第1部分(此選擇顯示在圖片中)，則欄位將成為：
bwbw
bwww
瓦布
瓦布
游戲的目標是翻轉所有的棋子，白色的一面向上或所有的碎片黑色的一面向上，您將撰寫一個程式，該程式將搜索實作此目標所需的最小輪數，
- 那么首先我用的是BFS解 2.判重用康拓展開，把狀態轉換成排列序號的來
-
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef struct table {
int pic[6][6];
}table;table start; //初始狀態
int P[16] = { 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768 };
bool vis[65536]; //狀態陣列
int dist[65536];
queue<table>Q;
//黑0 白1
char Negate(int ch)
{
if (ch)
return 0;
return 1;
}void turn(int x, int y, table& T)
{
T.pic[x][y] = Negate(T.pic[x][y]); //自身
T.pic[x][y - 1] = Negate(T.pic[x][y - 1]); //左側
T.pic[x][y + 1] = Negate(T.pic[x][y + 1]); //右側
T.pic[x - 1][y] = Negate(T.pic[x - 1][y]); //上側
T.pic[x + 1][y] = Negate(T.pic[x + 1][y]); //下側
}int get_dec(table T) //位壓縮
{
int dec = 0;
int s = 0;
for (int i = 4; i > 0; --i)
for (int j = 4; j > 0; --j)
{
dec += T.pic[i][j] * P[s];
s++;
}
return dec;
}int BFS()
{
Q.push(start); //初始狀態入隊
int st = get_dec(start); //獲取索引
vis[st] = true;
int front = 1, rear = 2;
table Now;
while (front < rear)
{
Now = Q.front(); //頭結點出隊
Q.pop();
int index = get_dec(Now); //獲取索引
if (index == 0 || index == 65535) //找到終點
return front;
for (int i = 0; i < 16; ++i)
{
int x = i / 4 + 1; //橫坐標
int y = i % 4 + 1; //縱坐標
table Next = Now;
turn(x, y, Next); //變換求下一步
int ni = get_dec(Next);
if (!vis[ni])
{
vis[ni] = true;
Q.push(Next);
dist[rear] = dist[front] + 1;
rear++;
}
}
front++;
}
return -1;
}int main() {
for (int i = 0; i < 6; ++i)
for (int j = 0; j < 6; ++j)
start.pic[i][j] = 0;
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= 4; ++i)
for (int j = 1; j <= 4; ++j)
{
char ch;
cin >> ch;
if (ch == 'w')
start.pic[i][j] = 0;
else
start.pic[i][j] = 1;
}int s = BFS();
if (s != -1)
cout << dist[s] << endl;
else
cout << "Impossible" << endl;
return 0;
}
-
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/71520.html
標籤：C++