POJ 1184 bfs+剪枝

文章目录[x]
  1. 1:原题链接:
  2. 2:题意:
  3. 3:思路:
  4. 3.1:所以:
  5. 4:参考代码:


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

原题链接:

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

题意:

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

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

思路:

  • 刚开始的时候没想到搜索,在想着如何贪心,考虑最优的选择得到最少操作数,但是发现没有类似最优子结构的东西,也就不能了。
  • 于是想到了,搜索(也就是),就是考虑从初始状态到达最终状态嘛,就是状态可达的性质,也是最小操作数,但是直接这样显然空间时间都是有问题的,因为有个位置*个不同的数=个状态,所以必须考虑剪枝:
  • 我们不难知道,这六种操作对一个数只有两种影响,一种是交换两个数位的位置,另一种是改变某个数位的值。
  • 所以,当且仅当光标到达某一数位,对这一数位的值的改变才可能发生。所以全部操作可分为两种:一种是移位和交换操作,一种是增大和减小操作。

所以:

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

参考代码:

// 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;
}


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像