Anonymous user
Knight's tour: Difference between revisions
Improved C++ code
(Improved C++ code) |
(Improved C++ code) |
||
Line 30:
array<array<int, N>, N> data;
array<pair<int, int>, 8> moves;
Board() {
Line 43 ⟶ 42:
}
array<int, 8> sortMoves(const int x, const int y) const {
array<tuple<int, int>, 8> counts;
for (int i = 0; i < 8; i++) {
const int dx = get<0>(moves[i]);
const int dy = get<1>(moves[i]);
int c = 0;
for (int j = 0; j < 8; j++) {
const int x2 = x + dx + get<0>(moves[j]);
const int y2 = y + dy + get<1>(moves[j]);
if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= N ||
data[y2][x2] != 0)
Line 72 ⟶ 71:
}
void solve(const string start) {
for (int v = 0; v < N; v++)
for (int u = 0; u < N; u++)
data[v][u] = 0;
const int x0 = start[0] - 'a';
const int y0 = N - (start[1] - '0');
data[y0][x0] = 1;
array<tuple<int, int, int, array<int, 8>>, N*N> order;
order[0] = make_tuple(
int n = 0;
while (n < N*N-1) {
const int x = get<0>(order[n]);
const int y = get<1>(order[n]);
bool ok = false;
for (int i = get<2>(order[n]); i < 8; i++) {
const int dx = moves[get<3>(order[n])[i]].first;
const int dy = moves[get<3>(order[n])[i]].second;
if (x+dx < 0 || x+dx >= N || y+dy < 0 || y+dy >= N)
Line 101 ⟶ 98:
if (data[y + dy][x + dx] == 0) {
get<2>(order[n]) = i + 1;
n++
data[y+dy][x+dx] = n+1;
order[n] = make_tuple(x+dx, y+dy, 0,
| |||