Solitaire

BFS

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
bool vis[8][8][8][8][8][8][8][8];             //标记
int g[10][10];                                //终点逻辑
int fx[][2] = { 1,0,-1,0,0,1,0,-1 };          //左右上下
struct node {
  int x[4], y[4]; 
  int step;
}s, e;
bool check(node a) {                          //判断是否四枚都到终点
  for (int i = 0; i < 4; ++i)
    if (!g[a.x[i]][a.y[i]])return 0;
  return 1;
}
bool judge(node a) {                          //考虑边界和是否走过
  for (int i = 0; i < 4; ++i)
    if (a.x[i] < 0 || a.x[i] >= 8 || a.y[i] < 0 || a.y[i] >= 8)return 1;
  if (vis[a.x[0]][a.y[0]][a.x[1]][a.y[1]][a.x[2]][a.y[2]][a.x[3]][a.y[3]])return 1;
  return 0;
}
bool empty(node a, int k) {                   //判断下一位置是否为空
  for (int i = 0; i < 4; ++i)
    if (i != k && a.x[i] == a.x[k] && a.y[i] == a.y[k]) return 0;            //不是当前那一枚与其它三枚比较
  return 1;
}
bool bfs() {
  memset(vis, 0, sizeof vis);                 //初始化
  queue<node>q;                               //初始化队列
  node a, b;
  a.step = 0;
  for (int i = 0; i < 4; ++i) {               //起点的棋子位置存放到a里
    a.x[i] = s.x[i];
    a.y[i] = s.y[i];
}
  q.push(a);
  vis[a.x[0]][a.y[0]][a.x[1]][a.y[1]][a.x[2]][a.y[2]][a.x[3]][a.y[3]] = 1;             //标记
  while (!q.empty()) {
    a = q.front(); q.pop();
    if (a.step >= 8)return 0;                 //超过8步
    if (check(a))return 1;
    for (int i = 0; i < 4; ++i)               //四枚棋子
      for (int j = 0; j < 4; ++j) {           //四个方向
        b = a; //
        b.x[i] += fx[j][0]; b.y[i] += fx[j][1];                                         //移动
        b.step++;                             //步长+1
        if (judge(b))continue;
        if (empty(b, i)) {                    //下一格为空
          if (check(b))return 1;
            vis[b.x[0]][b.y[0]][b.x[1]][b.y[1]][b.x[2]][b.y[2]][b.x[3]][b.y[3]] = 1;    //标记
            q.push(b);                       //放进队列
          }
        else {                               //不为空，要再走一步
          b.x[i] += fx[j][0]; b.y[i] += fx[j][1];                                       //再移动
          if (judge(b) || !empty(b, i))continue;                                        //过边界，过两格不允许
          if (check(b))return 1; 
          vis[b.x[0]][b.y[0]][b.x[1]][b.y[1]][b.x[2]][b.y[2]][b.x[3]][b.y[3]] = 1;///标记
          q.push(b);                         //放进队列
        }
      }
  }
  return 0;
}
int main() {
  while (cin >> s.x[0] >> s.y[0]) {          //输入起始的四枚棋子坐标
    s.x[0]--;s.y[0]--;                       //必须减1，不然内存会超
    for (int i = 1; i < 4; ++i) {
      cin >> s.x[i] >> s.y[i];
      s.x[i]--;s.y[i]--;
    }
    memset(g, 0, sizeof g);
    for (int i = 0; i < 4; ++i) {             //输入结束的四枚棋子的坐标
      cin >> e.x[i] >> e.y[i];
      e.x[i]--;e.y[i]--;
      g[e.x[i]][e.y[i]] = 1;                  //终点逻辑判断
    }
    bool flag = bfs();
    if (flag)cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  return 0;
}

笔记：棋局只有64×63×62×61≈1500万种，四枚棋子，有16种走法，连续走8次，有16⁸种可能，远远超过棋局总数，即使有标记也很浪费时间

双向广搜

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>
#include<queue>
using namespace std;
int fx[][2] = { 0,1,0,-1,1,0,-1,0 };
struct node {
  int p[4], step;
  bool check(int v) {                       //检测棋子的位置
    for (int i : p)                         //数组p依次取出元素赋值给整型变量i
      if (i == v)return 1;
    return 0;
  }
  int hash() {                             //压缩：哈希值
    int a[4];
    memcpy(a, p, sizeof a);                //a复制p
    sort(a, a + 4);                        //排序
    int res = 0;
    for (int i : a)res = res * 100 + i;    //数组转化字符串
    return res;
  }
};
unordered_set<int>st[2];                   //集合
queue<node>q[2];                           //起点终点队列
void clear() {
  for (int i = 0; i < 2; ++i) {
    queue<node>tmpp;
    swap(q[i], tmpp);                      //交换两个队列的内容
    st[i].clear();                         //清空哈希值
  }
}
bool flag(int i, int hash) {               //队列下标和待查hash
  if (st[i].find(hash) != st[i].end())return 1;                   //相遇--find():如果找到指定元素，它返回元素的迭代器，如果找不到指定元素，则返回指向unordered_set::end()的迭代器
  return 0;
}
bool bfs() {
  while (!q[0].empty() || !q[1].empty()) {
    for (int i = 0; i < 2; ++i) {          //两个队列
      if (!q[i].empty()) {
        node tmp = q[i].front(); q[i].pop();
        tmp.step++;
        for (int j = 0; j < 4; ++j) {     //四个点
          int x = tmp.p[j] / 10, y = tmp.p[j] % 10;
          for (int k = 0; k < 4; ++k) {   //四个方向
            int dx = x + fx[k][0], dy = y + fx[k][1];           //下一步
            if (dx >= 1 && dx <= 8 && dy >= 1 && dy <= 8 && tmp.check(dx * 10 + dy))                       //有障碍
              dx += fx[k][0], dy += fx[k][1]; //跳到下一个
            if (dx >= 1 && dx <= 8 && dy >= 1 && dy <= 8 && !tmp.check(dx * 10 + dy) && tmp.step <= 4) {   //满足条件：1.没出界、2.不重合棋子、3.不超步数
              tmp.p[j] = dx * 10 + dy;        //更新棋子位置
              if (st[i].find(tmp.hash()) == st[i].end()) {     //剪枝：判重
                if (flag(!i, tmp.hash()))return 1; 
                q[i].push(tmp); st[i].insert(tmp.hash());      //入队，入集合
              }
            }
          }
          tmp.p[j] = x * 10 + y;              //回溯
        }
      }
    }
  }
  return 0;
}
int main() {
  while (true) {
    clear();
    node tmp; tmp.step = 0;
    for (int k = 0; k < 2; ++k) {           //起始结束
      for (int i = 0; i < 4; ++i) {         //四组坐标
        tmp.p[i] = 0;
        for (int j = 0; j < 2; ++j) {       //xy坐标数值
          int x; if (scanf("%d", &x) == EOF)exit(0);
          tmp.p[i] = tmp.p[i] * 10 + x;//x*10+y
        }
      }
      q[k].push(tmp);
      st[k].insert(tmp.hash());             //插入哈希
    }
    if (flag(0, q[1].front().hash()) || bfs()) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  return 0;
}

笔记：双向广搜是开始和结束同时搜索，8步最多搜索 2 × 16⁴种棋局比单纯的BFS要快很多

版权声明：

本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/qq_49494204/article/details/110409767