Nguồn đề bài: http://vn.spoj.com/problems/KCOLLECT/
1. Đề bài KCOLLECT spoj
Công việc buôn bán dừa của Pirate không mấy khả quan cho lắm, khiến anh đêm ăn không ngon ngày ngủ không yên, chỉ biết chúi đầu vào xem “Rôbô trái cây”. Một ngày nọ, đang nằm ngủ dưới gốc dừa, bỗng một trái dừa rơi vào đầu anh ấy. Cũng giống như Newton, Pirate cũng cầm trái dừa lên, ngắm nghía và… rủa: “Khỉ thật, sao xứ này toàn là dừa thế này!”. Tức điên lên, Pirate quyết trồng thêm các loại trái cây khác vào hòn đảo của mình.
Đến mùa thu hoạch, Pirate đặt hàng một “Rôbô trái cây” để giúp mình hái quả. Khu vườn của Pirate có hình chữ nhật, và được chia thành M x N ô vuông bằng nhau. Trong mỗi ô vuông có một cây thuộc một loại quả khác nhau, đánh số từ 0 đến 9. Không phải vô tình mà chúng được đánh số như vậy, con số đó thể hiện giá trị kinh tế của các loại cây.
Tuy nhiên, nhìn mặt con Rôbô trái cây này có vẻ ngu ngu nên trong lần đầu tiên thử việc, Pirate muốn test AI của nó. Cụ thể là Rôbô phải tuân theo các quy định sau:
a. Tại mỗi ô, Rôbô chỉ có thể đi sang hướng đông hoặc hướng nam sang ô kề cạnh.
b. Có một số ô đặc biệt mà tại đó Rôbô có thể đi được thêm hướng tây hoặc hướng bắc sang ô kề cạnh (chỉ một trong hai).
c. Rôbô không được đi vào những ô có cây dừa (Pirate căm thù dừa).
d. Rôbô được đi qua một ô nhiều lần. Khi đi qua một ô, Rôbô phải hái hết quả ở cây trong ô đó. Lợi nhuận thu được sẽ bằng chỉ số của loại cây vừa được thu hái. Và sau này, không thể đạt thêm lợi nhuận gì từ ô đó nữa.
Xuất phát từ ô ở góc tây bắc của khu vườn, hãy giúp Rôbô trái cây xác định hành trình để đạt được lợi nhuận tối đa.
Input
- Dòng thứ nhất: ghi hai số nguyên M và N – kích thước của khu vườn.
- M dòng tiếp theo: mỗi dòng ghi N kí tự liên tiếp nhau mô tả khu vườn:
+ ‘0’ – ‘9’: các loại trái cây;
+ ‘#’: cây dừa;
+ ‘W’: được quyền đi theo hướng tây;
+ ‘N’: được quyền đi theo hướng bắc.
Output
- Ghi một số nguyên duy nhất là lợi nhuận tối đa đạt được.
Giới hạn
- Trong mọi test, 1 ≤ M, N ≤ 100.
- 60% số test có 1 ≤ M, N ≤ 20.
Example
Input:
2 3
264
3WW
Output:
15
Giải thích: Rôbô sẽ đi theo hành trình như sau (1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (2, 2) -> (2, 1) (ô (i, j) là ô ở dòng i và cột j). Tổng lợi nhuận sẽ là 2 + 6 + 4 + 3 = 15.
2. Hướng dẫn Kcollect spoj
Coi mỗi ô là một đỉnh, tìm số thành phần liên thông mạnh, đánh dấu những ô thuộc thành phần liên thông mạnh đó, coi mỗi thành phần liên thông mạnh là một đỉnh của đồ thị mới, định chiều đồ thị, vì đây là đồ thị có hướng ko chu trình nên ta tìm đường đi dài nhất bằng sắp xếp topo để đánh số đồ thị, sau đó áp dụng quy hoạch động tìm đường đi dài nhất . Có thể tham khảo thêm phần sắp xếp topo trong quyển một số vấn đề đáng chú ý môn tin học để hiểu rõ
3. Code tham khảo Kcollect spoj
uses math;
const fi = 'KCOLLECT.inp';
fo = 'KCOLLECT.out';
max = 1000000;
d : array[1..2] of longint = (0, 1);
c : array[1..2] of longint = (1, 0);
type banghi = record
x, y : longint;
end;
var
s : array[1..100, 1..100] of char;
free : array[1..100, 1..100] of longint ;
number, low : array[1..100,1..100] of longint;
tong , u, v, deg, num , a, q: array[1..max] of longint;
head, f : array[0..max] of longint;
adj : array[1..10000000] of longint;
visited : array[1..max] of boolean;
stack : array[1..max] of banghi;
n, count, componentcount, top, m, id : longint;
procedure readf;
var
i, j : longint;
begin
//assign(input, fi); reset(input);
//assign(output,fo); rewrite(output);
readln(m ,n);
for i := 1 to m do
for j := 1 to n do
if j <> n then read(s[i,j]) else readln(s[i,j]);
end;
procedure init;
begin
fillchar(number, sizeof(number), 0);
fillchar(free, sizeof(free), 0);
top := 0;
count := 0;
componentcount := 0;
end;
procedure push(x, y : longint);
begin
inc(top);
stack[top].x := x;
stack[top].y := y;
end;
function pop : banghi ;
begin
pop := stack[top];
dec(top);
end;
procedure visit(x, y:longint); {tim kiem theo chieu sau bat dau tai u}
var
i , a1, a2 : longint; res : banghi;
begin
inc(count); number[x, y] := count; { danh stt tham u}
low[x, y] := count ; {tam thoi coi u co cung toi u }
push(x, y);
for i := 1 to 2 do
begin
a1 := x + d[i];
a2 := y + c[i];
if (a1 <= m ) and (a2 <= n) and (free[a1, a2] = 0) and (s[a1,a2] <> '#') then
if number[a1, a2] <> 0 then { neu ma v da tham }
low[x, y] := min(low[x, y], number[a1, a2]) {giam low[u] nho nhat co the }
else { neu v chua tham }
begin
visit(a1, a2) ; { tham v }
low[x, y] := min(low[x, y], low[a1, a2]);
end;
end;
if s[x,y] = 'W' then
begin
a1 := x;
a2 := y - 1;
if (a1 >= 1) and (a2 >= 1) and (free[a1,a2] = 0 ) and (s[a1,a2] <> '#') then
if number[a1, a2] <> 0 then { neu ma v da tham }
low[x, y] := min(low[x, y], number[a1, a2]) {giam low[u] nho nhat co the }
else { neu v chua tham }
begin
visit(a1,a2) ; { tham v }
low[x, y] := min(low[x, y], low[a1, a2]);
end;
end;
if s[x,y] = 'N' then
begin
a1 := x - 1;
a2 := y ;
if (a1 >= 1) and (a2 >= 1) and (free[a1,a2] = 0 ) and (s[a1,a2] <> '#') then
if number[a1, a2] <> 0 then { neu ma v da tham }
low[x, y] := min(low[x, y], number[a1, a2]) {giam low[u] nho nhat co the }
else { neu v chua tham }
begin
visit(a1,a2) ; { tham v }
low[x, y] := min(low[x, y], low[a1, a2]);
end;
end;
{ sau khi chay het vong nay ta thay moi dinh thuoc DFS goc u da tham}
if low[x, y] = number[x, y] then { neu u la chot }
begin
inc(componentcount);
repeat
res := pop;
free[res.x, res.y] := componentcount;
if s[res.x, res.y] in ['0'..'9'] then
tong[componentcount] := tong[componentcount] + ord(s[res.x, res.y]) - 48;
until (res.x = x) and (res.y = y)
end;
end
procedure solve;
var
dem, i, j : longint;
begin
for i := 1 to m do
for j := 1 to n do
if (number[i, j] = 0) and (s[i,j] <> '#') then
visit(i, j);
end;
procedure creat;
var
i, j , k, a1, a2, dem : longint;
begin
dem := 0;
for i := 1 to m do
for j := 1 to n do
if s[i,j] <> '#' then
begin
for k := 1 to 2 do
begin
a1 := i + d[k];
a2 := j + c[k];
if (a1 <= m ) and (a2 <= n) and (s[a1,a2] <> '#') then
if (free[i,j] <> free[a1,a2]) then
begin
inc(dem);
u[dem] := free[i,j];
v[dem] := free[a1,a2];
inc(deg[free[i,j]]);
end;
end;
if s[i,j] = 'W' then
begin
a1 := i ;
a2 := j - 1;
if (a1 >= 1) and (a2 >= 1) and (s[a1,a2] <> '#') then
if (free[i,j] <> free[a1,a2]) then
begin
inc(dem);
u[dem] := free[i,j];
v[dem] := free[a1,a2];
inc(deg[free[i,j]]);
end;
end;
if s[i,j] = 'N' then
begin
a1 := i -1 ;
a2 := j ;
if (a1 >= 1) and (a2 >= 1) and (s[a1,a2] <> '#') then
if (free[i,j] <> free[a1,a2]) then
begin
inc(dem);
u[dem] := free[i,j];
v[dem] := free[a1,a2];
inc(deg[free[i,j]]);
end;
end;
end;
head[1] := 1;
for i := 2 to componentcount do
head[i] := head[i-1] + deg[i-1];
for i := 1 to dem do
begin
adj[head[u[i]]] := v[i];
inc(head[u[i]]);
end;
for i := 1 to componentcount do
dec(head[i]);
end;
procedure DFS(u: longint);
var
v : longint;
begin
visited[u] := true;
for v := head[u-1] + 1 to head[u] do
if (not visited[adj[v]]) then
DFS(adj[v]);
num[u] := id;
q[id] := u;
dec(id);
end;
procedure process;
var
u , i, j : longint;
begin
fillchar(visited,sizeof(visited),false);
id := componentcount;
for u:= 1 to componentcount do
if not visited[u] then DFS(u);
m := free[1,1];
fillchar(f, sizeof(f), 255);
f[q[componentcount]] := tong[q[componentcount]];
for i := componentcount - 1 downto 1 do
begin
for j := head[q[i]- 1] + 1 to head[q[i]] do
if f[adj[j]] >-1 then
if f[adj[j]] + tong[q[i]] > f[q[i]] then f[q[i]] := f[adj[j]] + tong[q[i]] ;
if f[q[i]] = -1 then f[q[i]] := tong[q[i]];
if q[i] = m then exit;
end;
end;
BEGIN
readf;
init;
solve;
creat;
process;
write(f[free[1,1]]);
END.
