История изменений
Исправление
pavlick,
(текущая версия)
:
Странно, что ты решал задачу быстро для поля из 7 клеток. Я тут тоже накостылил решение, 6 нормально решает, с семью не стал ждать.
#include <iostream>
#include <iterator>
#include <vector>
#include <array>
#include <unordered_set>
using namespace std;
constexpr int path_cnt = 1;
using pos_t = long;
constexpr pos_t miss = 100;
#define EXTR_X(pair) ((pair)>>32 & 0xffff)
#define EXTR_Y(pair) ((pair) & 0xffff)
#define SET_X(x, pair) ((pair) |= static_cast<pos_t>(x)<<32)
#define SET_Y(y, pair) ((pair) |= y)
template <int size>
array<pos_t, 8> get_steps(pos_t cur_pos) {
#define CHECK(val) ((val)>=size || (val)<0 ? miss : (val))
array<pos_t, 8> steps {};
pos_t x = EXTR_X(cur_pos);
pos_t y = EXTR_Y(cur_pos);
SET_X(CHECK(x-1), steps[0]);
SET_X(CHECK(x-1), steps[1]);
SET_X(CHECK(x+1), steps[2]);
SET_X(CHECK(x+1), steps[3]);
SET_X(CHECK(x-2), steps[4]);
SET_X(CHECK(x-2), steps[5]);
SET_X(CHECK(x+2), steps[6]);
SET_X(CHECK(x+2), steps[7]);
SET_Y(CHECK(y+2), steps[0]);
SET_Y(CHECK(y-2), steps[1]);
SET_Y(CHECK(y+2), steps[2]);
SET_Y(CHECK(y-2), steps[3]);
SET_Y(CHECK(y+1), steps[4]);
SET_Y(CHECK(y-1), steps[5]);
SET_Y(CHECK(y+1), steps[6]);
SET_Y(CHECK(y-1), steps[7]);
#undef CHECK
return steps;
}
template <int size>
void step_inter(vector<vector<pos_t>> &data, unordered_multiset<pos_t> &used) {
array<pos_t, 8> steps = get_steps<size>(data.back().back());
for (pos_t next : steps) {
if (data.size() > path_cnt)
return;
pos_t x = EXTR_X(next);
pos_t y = EXTR_Y(next);
if (x == miss || y == miss)
continue;
if (x == 0 && y == 0) {
if (data.back().size() != size*size)
continue;
data.push_back(data.back());
data.back().reserve(size*size);
data[data.size()-2].push_back(next);
break;
}
if ( used.contains(next) )
continue;
data.back().push_back(next);
used.insert(next);
step_inter<size>(data, used);
data.back().pop_back();
used.erase(next);
}
}
template <int size>
void step(vector<vector<pos_t>> &data) {
unordered_multiset<pos_t> used;
step_inter<size>(data, used);
}
int main() {
constexpr unsigned field_size = 7;
vector<vector<pos_t>> paths{ {0} };
paths.back().reserve(field_size*field_size);
step<field_size>(paths);
paths.pop_back();
for (auto &path : paths) {
cout << "--------path--------\n";
for (auto cell : path)
cout << EXTR_X(cell) << " " << EXTR_Y(cell) << endl;
}
return 0;
}
$ g++ -std=c++20 -O2 1.cc
field_size - задает размер поля.
path_cnt - количество закрытых путей, которые необходимо найти.
Для поля из 6 клеток:
--------path--------
0 0
1 2
0 4
2 5
1 3
0 5
2 4
3 2
2 0
0 1
2 2
4 1
5 3
4 5
3 3
5 4
3 5
1 4
0 2
1 0
3 1
5 0
4 2
3 4
5 5
4 3
5 1
3 0
1 1
0 3
1 5
2 3
4 4
5 2
4 0
2 1
0 0
Исходная версия
pavlick,
:
Странно, что ты решал задачу быстро для поля из 7 клеток. Я тут тоже накостылил решение, 6 нормально решает, с семью не стал ждать.
#include <iostream>
#include <iterator>
#include <vector>
#include <array>
#include <unordered_set>
using namespace std;
constexpr int path_cnt = 1;
using pos_t = long;
constexpr pos_t miss = 100;
#define EXTR_X(pair) ((pair)>>32 & 0xffff)
#define EXTR_Y(pair) ((pair) & 0xffff)
#define SET_X(x, pair) ((pair) |= static_cast<pos_t>(x)<<32)
#define SET_Y(y, pair) ((pair) |= y)
template <int size>
array<pos_t, 8> get_steps(pos_t cur_pos) {
#define CHECK(val) ((val)>=size || (val)<0 ? miss : (val))
array<pos_t, 8> steps {};
pos_t x = EXTR_X(cur_pos);
pos_t y = EXTR_Y(cur_pos);
SET_X(CHECK(x-1), steps[0]);
SET_X(CHECK(x-1), steps[1]);
SET_X(CHECK(x+1), steps[2]);
SET_X(CHECK(x+1), steps[3]);
SET_X(CHECK(x-2), steps[4]);
SET_X(CHECK(x-2), steps[5]);
SET_X(CHECK(x+2), steps[6]);
SET_X(CHECK(x+2), steps[7]);
SET_Y(CHECK(y+2), steps[0]);
SET_Y(CHECK(y-2), steps[1]);
SET_Y(CHECK(y+2), steps[2]);
SET_Y(CHECK(y-2), steps[3]);
SET_Y(CHECK(y+1), steps[4]);
SET_Y(CHECK(y-1), steps[5]);
SET_Y(CHECK(y+1), steps[6]);
SET_Y(CHECK(y-1), steps[7]);
#undef CHECK
return steps;
}
template <int size>
void step_inter(vector<vector<pos_t>> &data, unordered_multiset<pos_t> used) {
array<pos_t, 8> steps = get_steps<size>(data.back().back());
for (pos_t next : steps) {
if (data.size() > path_cnt)
return;
pos_t x = EXTR_X(next);
pos_t y = EXTR_Y(next);
if (x == miss || y == miss)
continue;
if (x == 0 && y == 0) {
if (data.back().size() != size*size)
continue;
data.push_back(data.back());
data.back().reserve(size*size);
data[data.size()-2].push_back(next);
break;
}
if ( used.contains(next) )
continue;
data.back().push_back(next);
used.insert(next);
step_inter<size>(data, used);
data.back().pop_back();
used.erase(next);
}
}
template <int size>
void step(vector<vector<pos_t>> &data) {
unordered_multiset<pos_t> used;
step_inter<size>(data, used);
}
int main() {
constexpr unsigned field_size = 7;
vector<vector<pos_t>> paths{ {0} };
paths.back().reserve(field_size*field_size);
step<field_size>(paths);
paths.pop_back();
for (auto &path : paths) {
cout << "--------path--------\n";
for (auto cell : path)
cout << EXTR_X(cell) << " " << EXTR_Y(cell) << endl;
}
return 0;
}
$ g++ -std=c++20 -O2 1.cc
field_size - задает размер поля.
path_cnt - количество закрытых путей, которые необходимо найти.
Для поля из 6 клеток:
--------path--------
0 0
1 2
0 4
2 5
1 3
0 5
2 4
3 2
2 0
0 1
2 2
4 1
5 3
4 5
3 3
5 4
3 5
1 4
0 2
1 0
3 1
5 0
4 2
3 4
5 5
4 3
5 1
3 0
1 1
0 3
1 5
2 3
4 4
5 2
4 0
2 1
0 0