POJ 1184 bfs+剪枝

csdn博客链接：https://blog.csdn.net/nuoyanli/article/details/105407577

原题链接：

http://poj.org/problem?id=1184

题意：

通过给定的六种操作将一个六位数变为另一个六位数，求需要的最少操作数。
六种操作：

左移和右移：将光标位置左移一位或右移一位，在第一位时无法左移，最后一位时无法右移。
左交换和右交换：将光标位置的数字与第一位或最后一位交换
增大和减小：将光标位置的数字增大或减小$1$

思路：

• 刚开始的时候没想到搜索，在想着如何贪心，考虑最优的选择得到最少操作数，但是发现没有类似最优子结构的东西，也就不能$dp$了。
• 于是想到了，搜索（也就是$bfs$），就是考虑从初始状态到达最终状态嘛，就是$bfs$状态可达的性质，也是最小操作数，但是直接这样显然空间时间都是有问题的，因为有$6$个位置*$1000000$个不同的数＝$6000000$个状态，所以必须考虑剪枝：

• 我们不难知道，这六种操作对一个数只有两种影响，一种是交换两个数位的位置，另一种是改变某个数位的值。
• 所以，当且仅当光标到达某一数位，对这一数位的值的改变才可能发生。所以全部操作可分为两种：一种是移位和交换操作，一种是增大和减小操作。

所以：

考虑到这两种交换操作都不涉及到$2,3,4,5$位置，所以这几个位置只能通过$up，down$来改变。
如果这几个位置是和目标状态是不一样的，那肯定是用$up，down$操作是最优的，而不会执行$left，right$操作，也就是上面说的，只有这几个位置在和目标状态一样时才做$left,right$操作。
这样剪枝之后，就可以直接搜索了：用字符串$s$存下数字，并把光标位置当做一个字符加到$s$末尾，用$map$标记当前状态是否出现过，然后$bfs$即可。

参考代码：

// nuoyanli
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

//#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define kB kush_back
#define FI first
#define SE second
//#define in
#define RI register
#define PB push_back
#define m_k(a, b) make_kair(a, b)
#define debug(a) cout << "---" << a << "---" << endl
#define debug_(a, b) cout << a << "---" << b << endl
const double pi = acos(-1.0);
const double eps = 1e-9;
typedef long long LL;
const int N = 2e6 + 10;
const int M = 1e3 + 10;
const LL mod = 1e9 + 9;
const LL inf = 0x3f3f3f3f;
const double f = 2.32349;
struct node {
  int step;
  string s;
} str;
string en;
map<string, int> mmp;
queue<node> q;
int bfs() {
  node t, tt;
  string temp;
  q.push(str);
  mmp[str.s] = 1;
  while (!q.empty()) {
    t = q.front();
    q.pop();
    if ((t.s).substr(0, 6) == en) {
      return t.step;
    }
    temp = t.s;
    swap(temp[0], temp[temp[6] - '0']); // S0
    if (!mmp.count(temp)) {
      tt.s = temp;
      tt.step = t.step + 1;
      q.push(tt);
      mmp[temp] = 1;
    }
    temp = t.s;
    swap(temp[5], temp[temp[6] - '0']); // S1
    if (!mmp.count(temp)) {
      tt.s = temp;
      tt.step = t.step + 1;
      q.push(tt);
      mmp[temp] = 1;
    }
    temp = t.s;
    if (temp[temp[6] - '0'] != '9' &&
        temp[temp[6] - '0'] != en[temp[6] - '0']) {
      temp[temp[6] - '0'] += 1; // U
    }
    if (!mmp[temp]) {
      tt.s = temp;
      tt.step = t.step + 1;
      q.push(tt);
      mmp[temp] = 1;
    }
    temp = t.s;
    if (temp[temp[6] - '0'] != '0' &&
        temp[temp[6] - '0'] != en[temp[6] - '0']) {
      temp[temp[6] - '0'] -= 1; // D
    }
    if (!mmp[temp]) {
      tt.s = temp;
      tt.step = t.step + 1;
      q.push(tt);
      mmp[temp] = 1;
    }
    temp = t.s;
    if (temp[6] != '0') { // L
      if (temp[6] != '5') {
        if (temp[temp[6] - '0'] == en[temp[6] - '0']) {
          temp[6] -= 1;
        }
      } else {
        temp[6] -= 1;
      }
    }
    if (!mmp[temp]) {
      tt.s = temp;
      tt.step = t.step + 1;
      q.push(tt);
      mmp[temp] = 1;
    }
    temp = t.s;
    if (temp[6] != '5') { // R
      if (temp[6] != '0') {
        if (temp[temp[6] - '0'] == en[temp[6] - '0']) {
          temp[6] += 1;
        }
      } else {
        temp[6] += 1;
      }
    }
    if (!mmp[temp]) {
      tt.s = temp;
      tt.step = t.step + 1;
      q.push(tt);
      mmp[temp] = 1;
    }
  }
}
void solve() {
  IOS;
  cin >> str.s >> en;
  mmp.clear();
  str.s = str.s + '0';
  str.step = 0;
  cout << bfs() << endl;
}
signed main() {
#ifdef in
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  solve();
  return 0;
}