首页 > > 程序设计 > C/C++ >

poj-1753题题解思路

2020-01-26 16:00:39来源：博客园阅读 ()

poj-1753题题解思路

今天天气很好！

首先题意是这样的：：

翻盖游戏是在一个长方形的4x4场上进行的，其16个方格中的每一个都放置了双面的棋子。每一块的一边是白色的，另一边是黑色的，每一块都是躺着的，要么是黑色的，要么是白色的。每一轮你翻转3到5块，从而改变他们的上边的颜色从黑色到白色，反之亦然。每一轮将翻转的棋子按照以下规则进行选择：

选择16件中的任何一件。
将选定的部分和所有相邻的部分翻转到左边、右边、顶部和所选部分的底部(如果有的话)。
以以下立场为例：

bwbw
瓦特
bbwb
bwwb
在这里，“b”表示其黑色一侧向上的部分，而“w”表示其白色一侧向上的部分。如果我们选择从第3行翻转第1部分(此选择显示在图片中)，则字段将成为：

bwbw
bwww
瓦布
瓦布
游戏的目标是翻转所有的棋子，白色的一面向上或所有的碎片黑色的一面向上。您将编写一个程序，该程序将搜索实现此目标所需的最小轮数。

那么首先我用的是BFS解

1. #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;
  }