CHESSCBG spoj – Bàn cờ thế

const fi='; H:array[1..4] of longint=(-1,4,-4,1); maxbit=66000; type data=word; var f:text; x,y:data; Q:array[0..maxbit] of data; C:array[0..maxbit] of data; sd:array[1..16] of data; D:array[1..16,1..4] of data; dau,cuoi:data; function getbit(k,x:data):byte; begin getbit:=(x shr (k-1)) and 1; end; procedure Setbit(c,k:byte; var x:data); begin if c=1 then x:=x or (1 shl (k-1)) else x:=x and (not (1 shl (k-1))); end; procedure docfile; var i,j:data; c:char; begin assign(f,fi); reset(f); x:=0; y:=0; for i:=1 to 16 do begin read(f,c); if c='1' then setbit(1,i,x); if i mod 4 = 0 then readln(f); end; for i:=1 to 16 do begin read(f,c); if c='1' then setbit(1,i,y); if i mod 4 = 0 then readln(f); end; close(f); end; procedure init; var i,j,dau,cuoi:data; tinh:integer; begin fillchar(sd,sizeof(sd),0); fillchar(d,sizeof(d),0); for i:=1 to 16 do begin dau:=1; cuoi:=4; if i and 3 = 1 then dau:=2 else if i and 3 = 0 then cuoi:=3; for j:=dau to cuoi do begin tinh:=i+h[j]; if tinh in [1..16] then begin inc(sd[i]); d[i,sd[i]]:=tinh; end; end; end; end; procedure themvao(x,y:data); begin inc(cuoi); Q[cuoi]:=x; c[x]:=y; end; function layra:data; begin layra:=q[dau]; inc(dau); end; Function gt(x,i: data):data; Begin if GetBit(i,x)=1 then exit(254); gt:=x; SetBit(1,i,gt); End; procedure bfs; var i,j,bit,tt:data; tinh:data; begin init; dau:=1; cuoi:=0; fillchar(c,sizeof(c),0); C[254]:=100; themvao(x,1); while (dau<=cuoi) do begin bit:=layra; tt:=c[bit]+1; for i:=1 to 16 do if getbit(i,bit)=1 then begin setbit(0,i,bit); for j:=1 to sd[i] do begin tinh:=gt(bit,d[i,j]); if c[tinh]=0 then begin themvao(tinh,tt); if c[y]<>0 then exit; end; end; setbit(1,i,bit); end; end; end; begin docfile; bfs; writeln(c[y]-1); end.

#include <bits/stdc++.h> using namespace std; int Start, End; int first, last; vector<int> Visit,d,mu2; queue<int> que; void Init() { ios_base::sync_with_stdio(false); mu2.resize(50); mu2[16]=1; for (int i=15;i>0;i--) { mu2[i]=mu2[i+1]*2; } char tg; for (int i=1;i<=16;i++) { cin>>tg; if(tg=='1') Start+=mu2[i]; } for (int i=1;i<=16;i++) { cin>>tg; if(tg=='1') End+=mu2[i]; } Visit.resize(mu2[1]*2+2); d.resize(mu2[1]*2+2); } void TryLeft(int u, int i) { int v=u-mu2[i]+mu2[i-1]; if(!Visit[v]) { que.push(v); d[v]=d[u]+1; Visit[v]=true; } } void TryRight(int u, int i) { int v=u-mu2[i]+mu2[i+1]; if(!Visit[v]) { que.push(v); d[v]=d[u]+1; Visit[v]=true; } } void TryUp(int u, int i) { int v=u-mu2[i]+mu2[i-4]; if(!Visit[v]) { que.push(v); d[v]=d[u]+1; Visit[v]=true; } } void TryDown(int u, int i) { int v=u-mu2[i]+mu2[i+4]; if(!Visit[v]) { que.push(v); d[v]=d[u]+1; Visit[v]=true; } } void Solve() { que.push(Start); Visit[Start]=true; while (!que.empty()) { int u=que.front(); que.pop(); if(u==End) { cout<<d[End]; return; } for (int i=1;i<=16;i++) { if((u&mu2[i])!=0) { if(i%4!=1 && (u&mu2[i-1])==0) TryLeft(u,i); if(i%4!=0 && (u&mu2[i+1])==0) TryRight(u,i); if(i>4 && (u&mu2[i-4])==0) TryUp(u,i); if(i<13 && (u&mu2[i+4])==0) TryDown(u,i); } } } } int main() { Init(); Solve(); }