Nguồn đề bài: CHESSCBG
Nội dung bài viết
1. Đề bài CHESSCBG spoj
Một bàn cờ thế là một bảng gồm 4 dòng, 4 cột. Mỗi thế cờ là một cách sắp xếp 8 quân cờ, hai quân khác nhau ở hai ô khác nhau. Bài toán đặt ra là cho hai thế cờ 1 và 2, hãy tìm một số ít nhất bước di chuyển quân để chuyển từ thế 1 sang thế 2; một bước di chuyển quân là một lần chuyển quân cờ sang ô trống kề cạnh với ô quân cờ đang đứng.
Dữ liệu vào
Từ file văn bản gồm 8 dòng, mỗi dòng là một xâu nhị phân độ dài 4 mà số 1/0 tương ứng với vị trí có hoặc không có quân cờ. Bốn dòng đầu là thế cờ 1, bốn dòng sau là thế cờ 2.
Dữ liệu ra
Gồm 1 dòng duy nhất là số bước chuyển quân ít nhất
Ví dụ
Dữ liệu vào:
1111
0000
1110
0010
1010
0101
1010
0101
Dữ liệu ra :
4
2. Code tham khảo CHESSCBG spoj
Pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 | 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. |
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #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(); } |
Bài viết liên quan
- BCISLAND PTIT spoj – Nước biển
- hướng dẫn EXPAR – spoj
- MTHCN spoj – Hình chữ nhật kì lạ
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- TNHWIFI spoj – Cafe wifi
- V8ORG spoj – Tổ chức đối lập
- LEM3 spoj – TRIP
- BCROBOT spoj PTIT – Đường đi rô-bốt
- BCLKCOUN spoj PTIT – Đếm số ao
- BCACM11D spoj PTIT – Đường nguyên tố