02/10/2018, 14:33
CIJEVI spoj – Cijevi
Nguồn đề bài: http://vn.spoj.com/problems/CIJEVI/ 1. Đề bài CIJEVI spoj Để giúp thiết kế một hệ thống ống dẫn dầu mới mà sẽ được dùng để vận chuyển dầu từ Nga đến Croatia, Zagreb và Moscow đang sử dụng một trò chơi có tên là Pipe Mania. Trong trò chơi này, Châu Âu được chia thành ...
Nguồn đề bài: http://vn.spoj.com/problems/CIJEVI/
1. Đề bài CIJEVI spoj
Để giúp thiết kế một hệ thống ống dẫn dầu mới mà sẽ được dùng để vận chuyển dầu từ Nga đến Croatia, Zagreb và Moscow đang sử dụng một trò chơi có tên là Pipe Mania. Trong trò chơi này, Châu Âu được chia thành R dòng và C cột. Mỗi ô vuông có thể là ô trống hoặc chứa một trong số bảy loại ống dẫn sau:
Dầu chảy từ Moscow đến Zagreb. Dầu có thể chảy theo cả hai chiều theo các ống dẫn. Ống loại ‘+’ là một loại đặc biệt mà dầu chỉ có thể chảy theo hai hướng (một là dọc, hai là ngang), như trong ví dụ sau:
Khi các ống dẫn dầu được đưa vào sử dụng, người ta phát hiện ra rằng các hackers xấu tính đã phá đi đúng một ống dẫn (thay nó bằng một ô trống).
Viết chương trình tìm xem ống bị phá nằm ở đâu và là loại nào.
Input
Dòng đầu chứa hai số nguyên R và C, là kích thước của Châu Âu (1 ≤ R, C ≤ 25)
Tiếp theo là R dòng chứa sơ đồ mô tả hệ thống ống dẫn, mỗi dòng chứa đúng C kí tự. Các kí tự là:
- Dấu chấm (‘.’), mô tả một ô trống;
- Các kí tự ‘|’ (ASCII 124), ‘-‘, ‘+’, ‘1’, ‘2’, ‘3’, ‘4’, mô tả các loại ống dẫn;
- Các chữ cái ‘M’ và ‘Z’, thể hiện Moscow và Zagreb. Mỗi chữ chỉ xuất hiện đúng một lần trong sơ đồ.
Dòng chảy của dầu đảm bảo là duy nhất; chính xác một ống dẫn nằm kề với Moscow cũng như Zagreb. Thêm vào đó, sơ đồ không hề có ống dẫn nào thừa (tất cả các ống dẫn trong sơ đồ đều phải được sử dụng sau khi thêm vào ống dẫn bị mất).
Dữ liệu đảm bảo luôn tồn tại lời giải, và lời giải đó là duy nhất.
Output
In ra cột và dòng của ống dẫn bị phát, và loại của ống dẫn đó (một trong số bay kí tự như trong dữ liệu).
Example
Input
3 7
…….
.M-.-Z.
…….
Output
2 4 –
Input
3 5
..1-M
1-+..
Z.23.
Output
2 4 4
Input
6 10
Z.1—-4..
|.|….|..
|..14..M..
2-+++4….
..2323….
……….
Output
3 3 |
2. Hướng dẫn Cijevi spoj
cách làm : Bài này duyệt DFS bình thường, cho dầu chảy, dừng lại ở đâu thì ta thay lần lượt các ống có thể, tiếp tục duyệt cho dầu chạy. đến khi gặp chữ Z thì kiểm tra, bằng cách dfs lại lần nữa, nếu tất cả ống đã qua thì write kq. Chủ yếu luyện code chứ không khó
3. Code tham khảo Cijevi spoj
const
d1 : array[1..4] of longint = (1, -1, 0, 0) ;
c1 : array[1..4] of longint = (0, 0, 1,-1) ;
var
n, m , resx, resy, x1, y1 : longint;
res : char;
ok , ktt : boolean;
a : array[0..26,0..26] of char ;
free : array[0..26,0..26] of boolean;
function inside(x, y : longint): boolean;
begin
if (x >= 1) and (y >= 1) and (x <= n ) and (y <= m) then exit(false) ;
exit(true);
end;
function kt : boolean;
var
i, j : longint;
begin
for i := 1 to n do
for j := 1 to n do
if a[i,j] in ['1', '2', '3', '4', '|', '+', '-'] then
if free[i,j] = false then exit(false);
exit(true);
end;
procedure dfs1(i, j, k : longint);
var
a1, a2 , ii: longint;
begin
if inside(i, j) then exit;
free[i,j] := true;
if a[i,j] = 'M' then
for ii := 1 to 4 do
begin
a1 := i + d1[ii];
a2 := j + c1[ii];
dfs1(a1,a2, ii);
end;
if a[i,j] = '.' then
begin
exit;
end;
if a[i,j] = '+' then
begin
if k = 1 then dfs1(i+1,j,1) ;
if k = 2 then dfs1(i-1,j,2) ;
if k = 3 then dfs1(i, j+ 1,3);
if k = 4 then dfs1(i, j- 1,4);
end;
if a[i,j] = '-' then
begin
if k = 3 then dfs1(i, j+ 1,3);
if k = 4 then dfs1(i, j- 1,4);
end;
if a[i,j] = '|' then
begin
if k = 1 then dfs1(i+1,j,1);
if k = 2 then dfs1(i-1,j,2);
end;
if a[i,j] = '1' then
begin
if k = 4 then dfs1(i+1,j,1);
if k = 2 then dfs1(i,j+1,3);
end;
if a[i,j] = '2' then
begin
if k = 1 then dfs1(i,j+1,3);
if k = 4 then dfs1(i-1,j,2);
end;
if a[i,j] = '3' then
begin
if k = 1 then dfs1(i, j-1,4);
if k = 3 then dfs1(i-1,j, 2);
end;
if a[i,j] = '4' then
begin
if k = 3 then dfs1(i+1, j ,1);
if k = 2 then dfs1(i, j-1, 4);
end;
if a[i,j] = 'Z' then
begin
if kt = true then ktt := true;
end;
end;
function check : boolean ;
begin
fillchar(free, sizeof(free), false);
dfs1(x1,y1, 1);
exit(ktt);
end;
procedure dfs(i, j, k : longint);
var
a1, a2 , ii: longint;
begin
if inside(i, j) then exit;
if a[i,j] = 'M' then
for ii := 1 to 4 do
begin
a1 := i + d1[ii];
a2 := j + c1[ii];
dfs(a1,a2, ii);
end;
if a[i,j] = '.' then
begin
if ok = true then
begin
ok := false;
if (k = 1) or ( k= 2) then
begin
a[i,j] := '|' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '+' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '1' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '2' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '3' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '4' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
end;
if (k = 3) or (k = 4) then
begin
a[i,j] := '-' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '+' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '1' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '2' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '3' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
a[i,j] := '4' ; resx := i; resy := j; res := a[i,j]; dfs(i,j,k);
end;
a[i,j] := '.';
ok := true;
end;
end;
if a[i,j] = '+' then
begin
if k = 1 then dfs(i+1,j,1) ;
if k = 2 then dfs(i-1,j,2) ;
if k = 3 then dfs(i, j+ 1,3);
if k = 4 then dfs(i, j- 1,4);
end;
if a[i,j] = '-' then
begin
if k = 3 then dfs(i, j+ 1,3);
if k = 4 then dfs(i, j- 1,4);
end;
if a[i,j] = '|' then
begin
if k = 1 then dfs(i+1,j,1);
if k = 2 then dfs(i-1,j,2);
if (k = 3) or (k = 4) then exit;
end;
if a[i,j] = '1' then
begin
if k = 4 then dfs(i+1,j,1);
if k = 2 then dfs(i,j+1,3);
end;
if a[i,j] = '2' then
begin
if k = 1 then dfs(i,j+1,3);
if k = 4 then dfs(i-1,j,2);
end;
if a[i,j] = '3' then
begin
if k = 1 then dfs(i, j-1,4);
if k = 3 then dfs(i-1,j, 2);
end;
if a[i,j] = '4' then
begin
if k = 3 then dfs(i+1, j ,1);
if k = 2 then dfs(i, j-1, 4);
end;
if a[i,j] = 'Z' then
begin
if check then
begin
write(resx, ' ', resy, ' ', res);
halt;
end;
end;
end;
procedure readf;
var
i , j : longint;
begin
readln(n, m);
for i := 1 to n do
for j := 1 to m do
begin
if j <> m then read(a[i,j]) else readln(a[i,j]);
if a[i,j] = 'M' then begin x1 := i; y1 :=j ; end;
end;
ok := true;
end;
procedure process;
begin
dfs(x1,y1,1) ;
end;
begin
// Assign(input, 'CIJEVI.inp'); reset(input);
readf;
process;
end.
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 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 | const d1 : array[1..4] of longint = (1, -1, 0, 0) ; c1 : array[1..4] of longint = (0, 0, 1,-1) ; var n, m , resx, resy, x1, y1 : longint; res : char; ok , ktt : boolean; a : array[0..26,0..26] of char ; free : array[0..26,0..26] of boolean; function inside(x, y : longint): boolean; begin if (x >= 1) and (y >= 1) and (x <= n ) and (y <= m) then exit(false) ; exit(true); end; function kt : boolean; var i, j : longint; begin for i := 1 to n do for j := 1 to n do if a[i,j] in ['1', '2', '3', '4', '|', '+', '-'] then if free[i,j] = false then exit(false); exit(true); end; procedure dfs1(i, j, k : longint); var a1, a2 , ii: longint; begin if inside(i, j) then exit; free[i,j] := true; if a[i,j] = 'M' then for ii := 1 to 4 do begin a1 := i + d1[ii]; a2 := j + c1[ii]; dfs1(a1,a2, ii); end; if a[i,j] = '.' then begin exit; end; if a[i,j] = '+' then begin if k = 1 then dfs1(i+1,j,1) ; if k = 2 then dfs1(i-1,j,2) ; if k = 3 then dfs1(i, j+ 1,3); if k = 4 then dfs1(i, j- 1,4); end; if a[i,j] = '-' then begin if k = 3 then dfs1(i, j+ 1,3); if k = 4 then dfs1(i, j- 1,4); end; if a[i,j] = '|' then begin if k = 1 then dfs1(i+1,j,1); if k = 2 then dfs1(i-1,j,2); end; if a[i,j] = '1' then begin if k = 4 then dfs1(i+1,j,1); if k = 2 then dfs1(i,j+1,3); end; if a[i,j] = '2' then begin if k = 1 then dfs1(i,j+1,3); if k = 4 then dfs1(i-1,j,2); end; if a[i,j] = '3' then begin if k = 1 then dfs1(i, j-1,4); if k = 3 then dfs1(i-1,j, 2); end; if a[i,j] = '4' then begin if k = 3 then dfs1(i+1, j ,1); if k = 2 then dfs1(i, j-1, 4); end; if a[i,j] = 'Z' then begin if kt = true then ktt := true; end; end; function check : boolean ; begin fillchar(free, sizeof(free), false); dfs1(x1,y1, 1); exit(ktt); end; procedure dfs(i, j, k : longint)
Có thể bạn quan tâm
0
|
