神机百炼2.42-状态压缩BFS

状态压缩BFS

• • 食用指南：
  • 题目描述：
  • 题目分析：
  • 算法原理：
  • • 模板算法：
    • 状态压缩：
    • • 1. 状态压缩后的形式：
      • 2. 状态附属信息的添加：
      • 3. 队列元素的改变：
  • 代码实现：
  • 代码误区：
  • • 1. 状态压缩下的状态树节点：
    • 2. 为什么swap(s[k], s[a*3+b])后还要swap回来？
    • 3. 读入string：
    • 4. unordered_map<>使用方法：
• 本篇感想：

食用指南：

对该算法程序编写以及踩坑点很熟悉的同学可以直接跳转到代码模板查看完整代码
只有基础算法的题目会有关于该算法的原理，实现步骤，代码注意点，代码模板，代码误区的讲解
非基础算法的题目侧重题目分析，代码实现，以及必要的代码理解误区

题目描述：

• 在一个 3×3 的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。
  例如：
  1 2 3
  x 4 6
  7 5 8
  在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

  我们的目的是通过交换，使得网格变为如下 排列（称为正确排列）：
  1 2 3
  4 5 6
  7 8 x
  例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

  交换过程如下：
  1 2 3 1 2 3 1 2 3 1 2 3
  x 4 6 4 x 6 4 5 6 4 5 6
  7 5 8 7 5 8 7 x 8 7 8 x
  现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

  输入格式
  输入占一行，将 3×3 的初始网格描绘出来。
  例如，如果初始网格如下所示：
  1 2 3
  x 4 6
  7 5 8
  则输入为：1 2 3 x 4 6 7 5 8

  输出格式
  输出占一行，包含一个整数，表示最少交换次数。
  如果不存在解决方案，则输出 −1。

  输入样例：
  2 3 4 1 5 x 7 6 8
  输出样例
  19

• 题目来源：https://www.acwing.com/problem/content/847/

题目分析：

• 状态题目 - 可以确定是BFS / DFS
• 最少变化步数 - BFS无疑
• 依托于队列BFS不难，难在网格状态的表达和存储
• 下面我们来讲解如何将复杂状态压缩为一个字符串或者数字的状态压缩算法，以及如何采用ordered_map<>为状态添加附属信息

算法原理： 模板算法：

• 传送门：BFS

状态压缩： 1. 状态压缩后的形式：

• 常见的状态压缩就是使用一个字符串或者一个数字存储一种状态

1. 字符串：
   本题的九宫格的所有状态可以用一个长度为9的string表示
   

   又如：目的状态是"12345678x"

   也可以从字符串还原回九宫格：
   行数 = len / 3
   列数 = len %3

2. 数字：
   假设现在有0 long long 整型刚好64位，每一位上1表示买，上0表示不买
   每次查看第x种物品是否购买，只需要将这个long long 右移x-1位后&1
   且long long 也可以表达出2ⁿ种状态

2. 状态附属信息的添加：

• STL中的unordered_map<泛型1， 泛型2>，泛型1为查找的键/索引，泛型2为对应的值

• 由于泛型可以存储任意数据结构，所以不论是为字符串还是数字添加附属信息，都直接使用unordered_map<>即可

• 时间复杂度：
  map采用的AVL树，平均插入查找都是O(logn)
  unordered_map<>采用的哈希表，平均插入查找都是O(1)

• 举例：
  起始九宫格是：“123x46758”，对应移动步数是0
  则unordered_map state
  state[“123x46758”] = 0;

  注意理解unordered_map<>是哈希表，非常长，且直接索引插入即可
  且插入元素在哈希表中存储的是备份，不是原本元素的地址

• 命名unordered_map<泛型1， 泛型2>
  由于泛型1是索引，我们主要想获取泛型2的附加信息
  所以将unordered_map<>命名为附件信息即可，如本题的变化步数/到起始状态的举例dis[]

3. 队列元素的改变：

• 队列元素就是状态数的节点，节点是什么类型则队列就是什么类型
• 在存储图中某点时，队列元素是pair
• 在存储状态时，队列元素是状态压缩后的字符串或者数字

代码实现：

#include 
#include 
#include 
#include 
using namespace std;

queue<string> q;
unordered_map<string, int> dis;

string target = "12345678x";
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int bfs(string start)
{
    q.push(start);
    dis[start] = 0;

    while(!q.empty())
    {
        auto s = q.front();
        q.pop();
        int distance = dis[s];

        int k = s.find('x');
        int x = k / 3, y = k % 3;
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a > -1 && a < 3 && b > -1 && b < 3)
            {
            	//由于map自身拷贝，所以我们不需要单独存储变化后的s，变化后的s直接在哈希表中拷贝了一份
                swap(s[k], s[a * 3 + b]);
                if(!dis.count(s))
                {
                    dis[s] = distance + 1;
                    q.push(s);
                    if (s == target) return dis[s];
                }
                swap(s[k], s[a * 3 + b]);
            }
        }
    }
    return -1;
}

int main()
{
    string c, s;
    for(int i = 0; i < 9; i++)
    {
        cin >> c;
        s += c;
    }
    cout <<bfs(s);
    return 0;
}

代码误区： 1. 状态压缩下的状态树节点：

• 本题所有状态都是九宫格的填写，将每个九宫格用一个string表示
  需要注意string中存放0-9无歧义，而存放10，11可能被解析为1,0,1,1
• 状态树：
  

2. 为什么swap(s[k], s[a*3+b])后还要swap回来？

• 在该节点可能发生4中交换：上下左右
• 由于unordered_map<>和queue<\string>自身存储的是添加节点的拷贝
  所以在当前字符串本地 *** 作即可
  swap()一次之后达到状态树子节点，放入哈希表 & queue存储
  再swap()回来

3. 读入string：

• 法一：字符串拼接，s1 + s2
• 法二：事先规定字符串长度，string s(length, ‘a’);或string s(“12345678x”);
• string自带find()函数，可以从头到尾查找string中的单个字符或者字符子串，返回索引
• rfind()从尾到头查找子串或单个字符

4. unordered_map<>使用方法：

• 由于该STL本质是一个很长的开放寻址法哈希表
• 所以本身再大的索引都有对应的节点，直接 dis[“键”] = 值;即可，不必push()/push_back()
• 删除哈希表中节点：
  dis.erase(键/迭代器) 来移除元素。移除成功则返回已移除的元素个数

本篇感想：

• 压缩后的状态表示和存储也不难，难点其实是STL中queue<> 和 unordered_map<>的使用
• 状态压缩除了在dfs bfs 中使用，在dp动态规划中也是经常出现的，所谓状态压缩dp
• dp我们会在后面讲
• 看完本篇博客，恭喜已登 《筑基境-初期》
  

距离登仙境不远了，加油