P1225 黑白棋游戏 题解

FHQ_Treap · 2024-08-06 11:55:37 · 题解

看到大佬们都用了 BFS+状态压缩+位运算，这里提供一个 BFS+简单状态压缩 的做法。

其实这题广搜也没什么难的，就是正常的广搜，只是我一开始写了结构体里传数组，CE 了，所以不得已用了一种稍微麻烦一点的做法。但也无伤大雅。

思路

先定义一个结构体（结构体乃日常广搜操作），然后整一个记录状态的 map，因为这次记录的有点不太一样，是一个字符串（因为我把数组压成字符串操作），所以不能用数组，每次遍历 16 个位置（4 \times 4 = 16），算出这个位置所在行数（下面会说怎么算），枚举相邻的格子，算出它在压缩后的字符串的位置（下面会说怎么算），交换这两个位置，如果当前的状态已经出现过，continue，否则将这个状态放进队列，更新步数和路径（之后会说），当当前队首的状态已经等于目标状态，那么输出步数和路径（之后会说）。

细节

• 将数组压成字符串的方法：每次读入一行，用一个字符串拼接即可，写成代码如下：

  a = ' '+a;//字符串下标从0开始，为了方便处理，加上一个没用的字符，就变成了从1开始
  for(int i = 0;i<=3;i++)
  {
        string s;
        cin >> s;
        a+=s;
  }

• 对于一个位置 i，我们如何算出它在原数组中的行数和列数呢？这其实很简单，首先我们设 x 表示位置 i 的行数，y 表示位置 i 的列数，当 y \not = 4 时，那么有 4 \times (x-1)+y = i 这个式子，这应该很容易想到，那么 x = \lfloor i \div 4 \rfloor+1，y = i \bmod 4，而当 y = 4 时，有 4 \times x = i 这个式子，那么 x = i \div 4，y = 1。写成代码就是：

  int x1 = i%4 == 0?i/4:i/4+1,y1 = i%4 == 0?4:i%4;

• 对于原来二维数组的一个位置 (i,j)，我们如何计算它在压缩后的字符串中的位置呢？很简单：答案就是 (x-1) \times 4+y，这个应该很好理解，这里便不再解释。

  int he = (x2-1)*4+y2;

• 记录路径就很简单了，直接把位置转成字符串再拼起来就行了，代码：

  string g = c.y+to_string(x1)+to_string(y1)+to_string(x2)+to_string(y2);
  q.push({d,g,c.cnt+1});

  关于输出路径

  输出路径还是非常简单的，我们只需要不断的输出我们的答案，当循环变量 (i+1) \bmod 4 = 0 时，换行即可。

  代码

  #include<bits/stdc++.h> 
  using namespace std; 
  map<string,int>m;
  struct node
  {
    string x;
    string y;
    int cnt;    
  };
  queue<node>q;
  string a,b;
  int dx[4] = {-1,1,0,0};
  int dy[4] = {0,0,-1,1};
  signed main()
  {
    a = ' '+a;
    b = ' '+b;
    for(int i = 0;i<=3;i++)
    {
        string s;
        cin >> s;
        a+=s;
    }                 
    for(int i = 0;i<=3;i++)
    {
        string s;
        cin >> s;         
        b+=s;
    }
    m[a] = 1;
    q.push({a,"",0});
    while(q.size())
    {
        node c = q.front();
        q.pop();        
        if(c.x == b)
        {
            printf("%d\n",c.cnt);
            for(int i = 0;i<c.y.size();i++)
            {
                cout << c.y[i];
                if((i+1)%4 == 0)
                {
                    cout << "\n";
                }
            }
            return 0;
        }     
        for(int i = 1;i<=16;i++)
        {
            int x1 = i%4 == 0?i/4:i/4+1,y1 = i%4 == 0?4:i%4;
            for(int j = 0;j<4;j++)
            {
                int x2 = x1+dx[j],y2 = y1+dy[j];
                if(x2>=1&&x2<=4&&y2>=1&&y2<=4)
                {
                    int hehe = i,he = (x2-1)*4+y2;
                    string d = c.x;
                    if(d[hehe] == d[he])
                    {
                        continue;
                    }
                    swap(d[hehe],d[he]);
                    if(m[d])
                    {
                        continue;
                    }
                    string g = c.y+to_string(x1)+to_string(y1)+to_string(x2)+to_string(y2);
                    q.push({d,g,c.cnt+1});
                    m[d] = 1;
                }
            }
        }
    }
    return 0;
  }