lời giải QBBISHOP spoj – VOI06 Quân tượng
Nguồn đề bài: http://vn.spoj.com/problems/QBBISHOP/ 1. Đề bài QBBISHOP spoj Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên ...
Nguồn đề bài: http://vn.spoj.com/problems/QBBISHOP/
1. Đề bài QBBISHOP spoj
Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.
Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,…, m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân
Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy.
Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.
Input
Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t.
Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.
Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Output
Gồm 1 dòng duy nhất là số nước đi tìm được
Example
Input:
8 3 7 2 1 4
5 4
3 4
4 7
Output:
3
2. Thuật toán QBBISHOP spoj
Xem mỗi ô (i, j) như là 1 đỉnh của đồ thị. 2 đỉnh (x1, y1) và (x2, y2) có cạnh nối nếu (x1 – y1 = x2 – y2) hoặc (x1 + y1 = x2 + y2), tức là cùng nằm trên 1 trong 2 đường chéo. Sau đó BFS như thường.
3. code tham khảo QBBISHOP spoj
[sociallocker]
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 | const fi='; nmax=205; cld:array[1..4] of shortint=(1,1,-1,-1); clc:array[1..4] of shortint=(1,-1,1,-1); type data=longint; dulieu=record u,v:data; end; var f:text; A:array[0..nmax+1,0..nmax+1] of byte; m,n,s,t,q,p:data; C:array[0..nmax+1,0..nmax+1] of data; H:array[0..nmax*nmax] of dulieu; dau,cuoi:data; procedure docfile; var i,j,u,v:data; begin assign(f,fi); reset(f); readln(f,n,m,p,q,s,t); for i:=1 to n do for j:=1 to n do a[i,j]:=0; for i:=0 to n +1 do begin A[0,i]:=3; A[n+1,i]:=3; A[i,0]:=3; a[i,n+1]:=3; end; for i:=1 to m do begin readln(f,u,v); a[u,v]:=2; end; close(f); end; procedure themvao(x,y:data); begin inc(cuoi); H[cuoi].u:=x; H[cuoi].v:=y; end; procedure layra(var x,y:data); begin x:=H[dau].u; y:=H[dau].v; inc(dau); end; procedure go(x,y,k:data); var u,v:data; begin u:=x; v:=y; while a[u,v]<>3 do begin if (A[u,v]=0) then begin c[u,v]:=c[x,y]+1; themvao(u,v); a[u,v]:=1; end; if a[u,v]=2 then exit; if (u=s) and (v=t) then begin writeln(c[s,t]); readln; halt; end; u:=u+cld[k]; v:=v+clc[k]; end; end; procedure bfs; var i,j,x,y:data; begin dau:=1; cuoi:=0; themvao(p,q); a[p,q]:=1; for i:=1 to n do for j:=1 to n do C[i,j]:=0; while not (dau>cuoi) do begin layra(x,y); for i:=1 to 4 do go(x,y,i); end; if c[s,t]=0 then writeln('-1'); end; begin docfile; bfs; end. |
[/sociallocker]
