首页
社区
课程
招聘
第六题 追凶者也
2018-12-13 02:26 2305

第六题 追凶者也

2018-12-13 02:26
2305

第六题 追凶者也

没时间写分析,看起来做出来的人也很多应该总会有其他人好好写的吧。以下都是在胡扯,想看认真的分析的去看其他人写的吧。

分析

WinMain 和窗口函数里调了两个看起来是空的的函数(0x401280和0x401020),显然有哪里不对劲,稍微翻翻可以看到有个 TLS callback,里面做了一些不知道是啥但反正肯定是在针对跟我们压根不打算运行这个程序的人无关的事情,外加把 0x401280 处改成跳到 0x401220 和一个没仔细看是什么地方改到 0x401A10 处的事情。稍微翻翻就可以意识到 0x401A10 处看上去是个验证逻辑,这里面有两个验证。

 

第一个调用了 0x401290,传入了输入字符串和输入的长度,大致看一看会发现它初始化了一个 3x3 的棋盘,填上{4 1 3 7 2 5 8 6 0},要求输入里的每两个字符都形如 [wsad][1-8],找到第二位的数字,然后验证上下左右对应的方向是不是0,是的话交换一下。最后验证终止状态是不是 {1 2 3 4 5 6 7 8 0}。看起来就是个八数码。

 

第二个是检查了输入的某种校验和必须是 0x5634D252。

解决

#include <bits/stdc++.h>

using namespace std;

const int kFact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
const int kGoal = 46233;
const int kDeltaX[4] = {-1, 1, 3, -3};
const int kBadRow[4] = {-1, -1, 2, 0};
const int kBadCol[4] = {0, 2, -1, -1};
const char kOpName[4] = {'d', 'a', 'w', 's'};

struct State {
  array<char, 9> n;
  string answer;

  int rank() const {
    int h = 0;
    for (int i = 0; i < 9; i++)
      for (int j = i + 1; j < 9; j++)
        if (n[j] < n[i])
          h += kFact[8 - i];
    return h;
  }

  int xpos() const { return find(n.begin(), n.end(), 0) - n.begin(); }

  State move(int to) {
    State res = *this;
    int from = xpos();
    res.answer += kOpName[find(kDeltaX, kDeltaX + 4, to - from) - kDeltaX] +
                  to_string(res.n[to]);
    swap(res.n[from], res.n[to]);
    return res;
  }
};

int h(const string &str) {
  int h = str.length();
  for (auto c : str) {
    h = (h >> 28) ^ (h << 4) ^ c;
  }
  return h;
}

optional<string> bfs(const array<char, 9> &start) {
  queue<State> q;
  bool vis[362880] = {0};
  auto step = [&](const State &nxt) {
    int r = nxt.rank();
    if (vis[r])
      return;
    vis[r] = true;
    q.push(nxt);
  };
  step({start});

  while (!q.empty()) {
    auto cur = q.front(); q.pop();
    int nx = cur.xpos();
    for (int i = 0; i < 4; i++) {
      if (kBadRow[i] != -1 && nx / 3 == kBadRow[i])
        continue;
      if (kBadCol[i] != -1 && nx % 3 == kBadCol[i])
        continue;

      auto nxt = cur.move(nx + kDeltaX[i]);
      if (nxt.rank() == kGoal)
        return nxt.answer;
      step(nxt);
    }
  }
  return {};
}

int main(void) {
  auto _ = bfs({4, 1, 3, 7, 2, 5, 8, 6, 0});
  assert(_.has_value());
  string answer = _.value();
  assert(h(answer) == 0x5634D252);
  cout << answer << endl;
  return 0;
}

[培训]《安卓高级研修班(网课)》月薪三万计划

收藏
点赞3
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回