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.
