Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
ボタンを押すとそのボタンと周囲4近傍のボタンの ON/OFF が反転して,全てのボタンを ON にすればクリアのあのゲームを解くやつ
#include <iostream>
#include <queue>
#include <vector>
#include <array>
#include <map>
#include <bitset>
#include <utility>
#include <algorithm>
const int inf = 1e9;
using state = std::pair<int, int>;
int main (void) {
const int start = 0b000000000; // 初期状態
const int goal = 0b111111111; // ゴール
const std::array<int, 9> revbits{
0b110100000,
0b111010000,
0b011001000,
0b100110100,
0b010111010,
0b001011001,
0b000100110,
0b000010111,
0b000001011
};
std::priority_queue<state, std::vector<state>, std::greater<state>> q;
q.push(std::make_pair(0, start));
std::map<int, int> previous;
for (int st = 0; st < (1 << 10) - 1; ++st)
previous[st] = -1;
std::map<int, int> distance;
for (int st = 0; st < (1 << 10) - 1; ++st)
distance[st] = inf;
distance[start] = 0;
std::map<int, int> te;
while (!q.empty()) {
const auto p = q.top();
q.pop();
int cost, now;
std::tie(cost, now) = p;
if (now == goal)
break;
for (unsigned int i = 0; i < revbits.size(); ++i) {
const int next = now ^ revbits[i];
const int newcost = cost + 1;
if (distance[next] > newcost) {
distance[next] = newcost;
previous[next] = now;
te[next] = i;
q.push(std::make_pair(newcost, next));
}
}
}
std::cout << distance[goal] << std::endl;
int now = goal;
while (now != start) {
const int nowte = te[now];
std::cout << nowte % 3 << "," << nowte / 3 << std::endl;
now = previous[now];
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment