CHESSCBG - Bàn cờ thế

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>

using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int tl;
string a, b;
int num[5][5], cnt;
vector<int> pos[20];
int Q[1 << 17], d[1 << 17];
bool was[1 << 17];

void Enter() {
    string s;
    int i, j, d;
    for(i=1; i<5; i++) {
        getline(cin, s);
        a = a + s;
    }
    for(i=1; i<5; i++) {
        getline(cin, s);
        b = b + s;
    }

    for(i=1; i<5; i++)
    for(j=1; j<5; j++)
        num[i][j] = ++cnt;
    int x, y;
    for(i=1; i<5; i++)
    for(j=1; j<5; j++) {
        for(d=0; d<4; d++) {
            x = i + dx[d]; y = j + dy[d];
            if (x<1 || y<1 || x>4 || y>4) continue;
            pos[16 - num[i][j]].push_back(16 - num[x][y]);
        }
    }
}

void BFS() {
    bitset<16> s (a);
    bitset<16> t (b);
    bitset<16> v;
    tl = t.to_ulong();
    int l = 1, r = 1, ul, vl, i, j, p;
    Q[1] = s.to_ulong();
    was[Q[1]] = true;
    while (l <= r) {
        ul = Q[l++];
        bitset<16> u (ul);
        for(i=0; i<16; i++)
        if (u[i] == 1) {
            for(j=0; j<pos[i].size(); j++) {
                p = pos[i][j];
                if (u[p] == 0) {
                    v = u;
                    v.flip(i); v.flip(p);
                    vl = v.to_ulong();
                    if (was[vl]) continue;
                    Q[++r] = vl;
                    was[vl] = true;
                    d[vl] = d[ul] + 1;
                    if (vl == tl) return;
                }
            }
        }
    }
}

int main()
{
    Enter();
    BFS();
    printf("%d", d[tl]);
    return 0;
}

Download