CHESSCBG - Bàn cờ thế

Tác giả: happyboy99x

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N

char s[20];
int start, end;
bool vst[(1 << 16)-1];
int I[] = {-1,0,0,1}, J[] = {0,-1,1,0};

#define on(x,i) ((x)&(1<<(i)))
#define off(x,i) (((x)&(1<<(i)))==0)
#define ton(x,i) ((x)|(1<<(i)))
#define toff(x,i) ((x)&(~(1<<(i))))

int main() {
#ifndef ONLINE_JUDGE
	freopen( "input.txt", "r", stdin );
	//freopen( "output.txt", "w", stdout );
#endif
	scanf("%s%s%s%s",s,s+4,s+8,s+12);
	start = (int) bitset<16>(string(s)).to_ulong();
	scanf("%s%s%s%s",s,s+4,s+8,s+12);
	end = (int) bitset<16>(string(s)).to_ulong();
	queue<int> qu; vst[start] = 1; qu.push(start);
	for(int step = 0; !qu.empty(); ++step) {
		rep(k,qu.size()) {
			int x = qu.front(); qu.pop();
			if(x == end) { printf("%d\n",step); return 0; }
			for(int i = 0; i < 16; ++i) {
				if(off(x,i)) continue;
				int r = (15-i)/4, c = (15-i)%4;
				rep(j,4) {
					int ii = r+I[j], jj = c+J[j];
					if(ii>=0&&jj>=0&&ii<4&&jj<4&&off(x,15-ii*4-jj)&&!vst[ton(toff(x,i),15-ii*4-jj)]) {
						vst[ton(toff(x,i),15-ii*4-jj)]=1;
						qu.push(ton(toff(x,i),15-ii*4-jj));
					}
				}
			}
		}
	}
	return 0;
}

Download