https://www.cnblogs.com/funwithwords/p/19158097
#include <stdio.h> #include <stdint.h> #include <string.h> #include <time.h> #include <immintrin.h> #include <xmmintrin.h> #include <set> #include "cwisstable.h"const char* NM[][4] = { {"曹","贼","真","爽"}, {"西","施"}, {"昭","君"}, {"貂","蝉"}, {"甄","姬"}, {"玉","环"}, {"美"}, {"美"}, {"美"}, {"美"} }; int W[] = { 2, 2, 2, 2, 2, 2, 1, 1, 1, 1 }; // 默认5个水平条，随后修改 int H[] = { 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int T[10]; // Type const int D[][2] = { {0, 1}, {0, -1}, {-1, 0}, {1, 0} }; // 后面有两处用下标判断移动方向enum { MAX = 3600 * 10000 }; struct State {uint8_t aa[10][2]; #define CCY aa[0][0] // 曹操的yint p; // 局面路径的previous #define cpy20(dst, src) _mm_storeu_si128((__m128i*)dst, _mm_loadu_si128((__m128i*)src)); *(int*)((uint8_t*)dst+16) = *(int*)((const uint8_t*)src+16)void operator= (const State& s) { cpy20(aa, s.aa); p = s.p; }void operator=(const char* s);void print(const char* s = ""); } q[MAX + 10 * 4]; // 最多40个move. MAX很大; 没判断qt < MAX int qh, qt = 1; // queue head, tailvoid State::operator= (const char* s) {int p = 6;for (int x = 3; x >= 0; x--)for (int y = 4; y >= 0; y--) {#define CASE(c, i) case c: aa[i][1] = x; aa[i][0] = y; break;switch (s[x * 5 + y]) {// 曹关张黄子龙(l)马CASE('c', 0) CASE('g', 1) CASE('z', 2) CASE('h', 3) CASE('l', 4) CASE('m', 5)case 'p':aa[p][1] = x; aa[p++][0] = y; break; // pawn }}static const char* S[] = { "gg", "zz", "hh", "ll", "mm" };for (int i = 0; i < 5; i++) if (strstr(s, S[i])) W[i+1] = 1, H[i+1] = 2;for (int i = 0; i < 10; i++) T[i] = W[i] * 2 + H[i] - 2; }#define set2DArrayByCoordInA(a, b, what) for (int i = 0; i < 10; i++) { \const int x = a[i][1], y = a[i][0]; \for (int yy = y; yy < y + H[i]; yy++) \for (int xx = x; xx < x + W[i]; xx++) b[yy][xx] = what; \ }void State::print (const char* s) {int idx[10] = {};const char* b[5][4] = {};set2DArrayByCoordInA(aa, b, NM[i][idx[i]++])for (int y = 0; y < 5; y++) {for (int x = 0; x < 4; x++) printf("%s", b[y][x] ? : " ");puts("");}printf("%s\n", s); }void print_path () { // 数组存的单链表就地翻转int prev = -1, next = -1, n = 0;for (int cur = qh; cur != -1; ++n) {next = q[cur].p; q[cur].p = prev;prev = cur; cur = next;}for (int p = 0; p != -1; p = q[p].p) q[p].print();printf("%d\n", n); }#pragma pack(1) struct {uint8_t b[5][4];uint64_t n; // unique numberuint8_t _[4]; } u __attribute__((aligned(32))); #pragma pack()#define Ah { \_mm256_store_si256((__m256i*)&u, _mm256_setzero_si256()); \set2DArrayByCoordInA(a, u.b, T[i]) \for (int y = 0; y < 5; y++) \for (int x = 0; x < 4; x++) u.n = u.n * 5 + u.b[y][x]; \ }#ifdef st CWISS_DECLARE_FLAT_HASHSET(Set, uint64_t); Set set = Set_new(MAX); #define if_ok_add_state if (ok) { cpy20(q[qt].aa, a); \Ah if (!Set_contains(&set, &u.n)) { Set_insert(&set, &u.n); q[qt++].p = qh; } \ } #else std::set<uint64_t> set; #define if_ok_add_state if (ok) { cpy20(q[qt].aa, a); \Ah if (set.find(u.n) == set.end()) { set.insert(u.n); q[qt++].p = qh; } \ } #endifint main (int argc, char* argv[]) {//q[0] = "pp zz""ccghh""ccgll""pp mm";q[0] = (argc == 2) ? argv[1] : "pzzpg""cc g""ccllm""phhpm";q[0].p = -1;uint8_t a[10][2] __attribute__((aligned(32)));cpy20(a, q[0].aa); #ifdef stAh Set_insert(&set, &u.n); #elseAh set.insert(u.n); #endifdouble tm = clock();for (; qh < qt; qh++) {if (q[qh].CCY == 3) { print_path(); break; }cpy20(a, q[qh].aa);uint8_t b[5][4] __attribute__((aligned(32))), overflow[12];_mm256_store_si256((__m256i*)b, _mm256_set1_epi8(1));set2DArrayByCoordInA(a, b, 0)int qt1 = qt;for (int j = 0; j < 4; j++) {int ok;for (int i = 0; i < 6; i++) {const int ox = a[i][1], oy = a[i][0];int x = (a[i][1] += D[j][0]), y = (a[i][0] += D[j][1]);if (x < 0 || x + W[i] > 4 || y < 0 || y + H[i] > 5) ok = 0;else { // D[]的顺序不能换!if (j == 0) { y = oy + H[i]; ok = b[y][x] && (W[i] == 1 || b[y][x + 1]); }else if (j == 1) ok = b[y][x] & (!(W[i] - 1) | b[y][x + 1]); // W[i]1或2; 不更快else if (j == 2) ok = b[y][x] & (!(H[i] - 1) | b[y + 1][x]);else { x = ox + W[i]; ok = b[y][x] && (H[i] == 1 || b[y + 1][x]); }}if_ok_add_statea[i][1] -= D[j][0]; a[i][0] -= D[j][1];}for (int i = 6; i < 10; i++) {const int ox = a[i][1], oy = a[i][0];int x = (a[i][1] += D[j][0]), y = (a[i][0] += D[j][1]);if (x < 0 || x + W[i] > 4 || y < 0 || y + H[i] > 5) ok = 0;else {if (j == 0) y = oy + H[i];else if (j == 3) x = ox + W[i];ok = b[y][x];}if_ok_add_statea[i][1] -= D[j][0]; a[i][0] -= D[j][1];}} #if 1int qt2 = qt - 1;if (qt2 > qt1 && q[qt2].CCY < q[qt1].CCY) { State t = q[qt1]; q[qt1] = q[qt2]; q[qt2] = t; } #endif}printf("%.6f %d\n", (clock() - tm) / CLOCKS_PER_SEC, qt);return 0; }
ttt