BCISLAND PTIT spoj - Nước biển

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCISLAND/

Nội dung bài viết

1. Đề bài BCISLAND spoj
2. Gợi ý BCISLAND spoj
3. code tham khảo BCISLAND spoj

1. Đề bài BCISLAND spoj

Trái đất nóng lên kéo theo mực nước biển dâng. Hòn đảo nhỏ Gonnasinka thuê bạn để dự báo trước hiểm họa này. Cho trước 1 lưới tọa độ thể hiện cao độ của đảo, hãy giúp họ tính toán xem nước biển dâng cao bao nhiêu thì hòn đảo sẽ bị chia cắt.

Input

Input gồm nhiều bộ test, mỗi bộ test bao gồm:

Dòng đầu ghi 2 số n, m là chiều dài và chiều rộng.
Sau đó là n dòng, mỗi dòng gồm m số, mỗi số cho biết độ cao của ô đó, giá trị 0 chỉ mực nước biển. Những ô giá trị 0 dọc theo đường viền và những ô số 0 liền kề những ô này chỉ mặt biển. Những ô có giá trị 0 còn lại (được bao bọc bởi các số > 0) là đất liền bên trong đảo nhưng có độ cao ngang mặt nước biển. Hòn đảo lúc đầu chưa bị chia cắt. Số n và m không lớn hơn 100 và độ cao không lớn hơn 1000.
Dòng cuối cùng của input chứa 2 số 0

Output

Với mỗi bộ test, in ra:

Case n: Island splits when ocean raises f feet. (Đảo bị chia khi nước biển dâng cao f feet)

Hoặc

Case n: Island never splits. (Đảo không bao giờ bị chia cắt)

Example

Input:
5 5

3 4 3 0 0

3 5 5 4 3

2 5 4 4 3

1 3 0 0 0

1 2 1 0 0

5 5

5 5 5 5 7

4 1 1 1 4

4 1 2 1 3

7 1 0 0 4

7 3 4 4 4
0 0

Output:
Case 1: Island never splits.
Case 2: Island splits when ocean rises 3 feet.

######################################

2. Gợi ý BCISLAND spoj

– Dùng thuật toán DFS để loang ra đếm số TLPT với mực nước là L nào đó. (L=[min(a[i,j])..max(a[i,j])])

– Nếu số thành phần liên thông lớn hơn 1 mà đó ko phải là nước biển thì đó là KQ bài toán.

Bài này mình ko biết phải viết hướng dẫn như thế nào nữa. 😀 các bạn coi code hoặc gợi ý đỡ vậy. 😀

3. code tham khảo BCISLAND spoj

const   fi='';
        nmax=100;
        cld:array[1..4] of shortint=(-1,1,0,0);
        clc:array[1..4] of shortint=(0,0,1,-1);

type    data=longint;
var
        f:text;
        A:array[-1..nmax+2,-1..nmax+2] of data;
        dd:array[-1..nmax+2,-1..nmax+2] of data;
        n,m,L:data;
        test,gtmin,gtmax:data;

procedure dfs(u,v:data);
var     x,y,i:data;
begin
        dd[u,v]:=1;
        for i:=1 to 4 do
                begin
                        x:=u+cld[i];
                        y:=v+clc[i];
                        if (dd[x,y]=0) and (a[x,y]<=L) then
                                DFS(x,y);
                end;
end;

procedure dfs2(u,v:data);
var     x,y,i:data;
begin
        dd[u,v]:=2;
        for i:=1 to 4 do
                begin
                        x:=u+cld[i];
                        y:=v+clc[i];
                        if dd[x,y]=0 then
                                dfs2(x,y);
                end;
end;

function check(x:data):boolean;
var     i,j,stplt:data;
begin
        L:=x;
        for i:=0 to m+1 do
                for j:=0 to n+1 do
                        dd[i,j]:=0;
        dfs(0,0);
        stplt:=0;
        for i:=1 to m do
                for j:=1 to n do
                        if dd[i,j]=0 then
                                begin
                                        inc(stplt);
                                        dfs2(i,j);
                                end;
        if stplt>1 then
                exit(true);
        exit(false);
end;


procedure xuli;
var     i,j,dau,cuoi,mid:data;
begin
        // dien so 0 xung qanh mang A
        for i:=0 to m+1 do
                begin
                        a[i,0]:=0;
                        a[i,n+1]:=0;
                end;
        for j:=0 to n+1 do
                begin
                        a[0,j]:=0;
                        a[m+1,j]:=0;
                end;
        // tao vien ko cho Loang ra ngoai bang
        for i:=-1 to m+2 do
                begin
                        dd[i,-1]:=1002;
                        dd[i,n+2]:=1002;
                end;
        for j:=-1 to n+2 do
                begin
                        dd[-1,j]:=1002;
                        dd[m+2,j]:=1002;
                end;
        for i:=gtmin to gtmax do
                if check(i) then
                        begin
                                writeln('Case ',test,': Island splits when ocean rises ',i,' feet.');
                                exit;
                        end;
        writeln('Case ',test,': Island never splits.');
end;


function min(a,b:data):data;
begin
        if a<b then exit(a); exit(b);
end;

function max(a,b:data):data;
begin
        if a>b then exit(a); exit(b);
end;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        test:=0;
        repeat
                readln(f,m,n);
                inc(test);
                gtmax:=-10000;
                gtmin:=10000;
                if (n=0) and (m=0) then break;
                for i:=1 to m do
                        begin
                                for j:=1 to n do
                                        begin
                                                read(f,a[i,j]);
                                                gtmax:=max(gtmax,a[i,j]);
                                                gtmin:=min(gtmin,a[i,j]);
                                        end;
                                readln(f);
                        end;
                xuli;
        until false;
        close(f);
end;

begin
        docfile;
end.

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

const fi='';

nmax=100;

cld:array[1..4] of shortint=(-1,1,0,0);

clc:array[1..4] of shortint=(0,0,1,-1);

type data=longint;

var

f:text;

A:array[-1..nmax+2,-1..nmax+2] of data;

dd:array[-1..nmax+2,-1..nmax+2] of data;

n,m,L:data;

test,gtmin,gtmax:data;

procedure dfs(u,v:data);

var x,y,i:data;

begin

dd[u,v]:=1;

for i:=1 to 4 do

begin

x:=u+cld[i];

y:=v+clc[i];

if (dd[x,y]=0) and (a[x,y]<=L) then

DFS(x,y);

end;

procedure dfs2(u,v:data);

var x,y,i:data;

begin

dd[u,v]:=2;

for i:=1 to 4 do

begin

x:=u+cld[i];

y:=v+clc[i];

if dd[x,y]=0 then

dfs2(x,y);

end;

function check(x:data):boolean;

var i,j,stplt:data;

begin

L:=x;

for i:=0 to m+1 do

for j:=0 to n+1 do

dd[i,j]:=0;

dfs(0,0);

stplt:=0;

for i:=1 to m do

for j:=1 to n do

if dd[i,j]=0 then

begin

inc(stplt);

dfs2(i,j);

end;

if stplt>1 then

exit(true);

exit(false);

end;

procedure xuli;

var i,j,dau,cuoi,mid:data;

begin

// dien so 0 xung qanh mang A

for i:=0 to m+1 do

begin

a[i,0]:=0;

a[i,n+1]:=0;

end;

for j:=0 to n+1 do

begin

a[0,j]:=0;

a[m+1,j]:=0;

end;

// tao vien ko cho Loang ra ngoai bang

for i:=-1 to m+2 do

begin

dd[i,-1]:=1002;

dd[i,n+2]:=1002;

end;

for j:=-1 to n+2 do

begin

dd[-1,j]:=1002;

dd[m+2,j]:=1002;

end;

for i:=gtmin to gtmax do

if check(i) then

begin

writeln('Case ',test,': Island splits when ocean rises ',i,' feet.');

exit;

end;

writeln('Case ',test,': Island never splits.');

end;

function min(a,b:data):data;

begin

if a<b then exit(a); exit(b);

end;

function max(a,b:data):data;

begin

if a>b then exit(a); exit(b);

end;

procedure docfile;

var i,j:data;

begin

assign(f,fi); reset(f);

test:=0;

repeat

readln(f,m,n);

inc(test);

gtmax:=-10000;

gtmin:=10000;

if (n=0) and (m=0) then break;

for i:=1 to m do

begin

for j:=1 to n do

begin

read(f,a[i,j]);

gtmax:=max(gtmax,a[i,j]);

gtmin:=min(gtmin,a[i,j]);

end;

readln(f);

end;

xuli;

until false;

close(f);

end;

begin

docfile;

end.

BCISLAND PTIT spoj – Nước biển

1. Đề bài BCISLAND spoj

Input

Output

Example

2. Gợi ý BCISLAND spoj

3. code tham khảo BCISLAND spoj

Bài viết liên quan

Trả lời Hủy