Bài tập "Hội chợ"

[QuynhMyDuyen]

Có bài này mới đem ra cho các bạn "chặt chém" đây (đề hơi dài, các bạn chịu khó đọc nhé):

Trong hội chợ người ta tổ chức n gian hàng được đánh số theo thứ tự từ 1 đến n. Mỗi gian hàng có thể có 1 hoặc nhiều cửa thông qua các gian hàng khác. Từ gian hàng thứ i có thể đến gian hàng thứ j và ngược lại nếu 2 gian hàng có cửa trực tiếp thông với nhau. Bản đồ thể hiện đường đi giữa các gian hàng trong hội chợ được cho trong tập tin txt Hoicho.inp gồm i+1 dòng với cấu trúc sau:
+ Dòng đầu gi số n (0<n<100) số gian hàng trong hội chợ.
+ n dòng còn lại thể hiện đường đi giữa các gian hàng. Trong đó:
Dòng i+1 (1<=i<=n) mỗi dòng gồm n số 0 hoặc 1. Trường hợp có đường đi trực tiếp từ i đến j kí hiệu là 1, không có đường đi kí hiệu là 0, từ i đến i kí hiệu là 0.
Viết chương trình làm các việc sau: Cho biết TẤT CẢ các gian hàng trong hội chợ có thông nhau hay không (từ gian hàng bất kì có thể đi đến tất cả các gian hàng khác). Nếu không thì cho người dùng nhập vào số t (1<=t<=n) cho biết từ gian hàng t có thể đến được những gian hàng nào. Kết quả xuất ra màn hinh.

Ví dụ 1: Hoicho.inp:
5
0 1 0 0 1
1 0 1 0 0
0 1 0 1 1
1 0 1 1 0
Kết quả: Cac gian hang trong hoi cho thong nhau.

Ví dụ 2: Hoicho.inp:
8
0 0 1 1 1 0 0 0
0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0
Kết quả: Cac gian hang trong hoi cho khong thong nhau.
Nhập t=3, xuất ra kết quả:
1 2 3 4 5

Đây là bài của tui, các bạn xem có sai gì không nhé:

Program Hoicho;
uses CRT;
const Fi='Hoicho.in';
var F:text;n:integer;a:array[1..100,1..100] of byte;
den:integer;b:array[1..100] of byte;
{------------------------------------------------}
Procedure nhap;
var i,j:integer;
begin
assign(F,Fi);
reset(F);
read(F,n);
for i:=1 to n do
for j:=1 to n do
read(F,a[i,j]);
close(F);
end;
{----------------------------------------------------}
Function KT(x:integer):boolean;
var i:integer;
begin
for i:=1 to den do
if x=b[i] then
begin
KT:=false;
exit;
end;
KT:=true;
end;
{-----------------------------------------------------}
Procedure tim(x:integer;var s:integer);
var i:integer;
begin
for i:=1 to n do
if (a[x,i]=1) and (KT(i)) then
begin
inc(s);
b[s]:=i;
end;
end;
{------------------------------------------------------}
Procedure xuat(x:integer);
var i:integer;
begin
tim(x,den);
for i:=1 to den do
tim(b[i],den);
end;
{------------------------------------------------------}
Procedure xuli;
var k:boolean;i,j,l,t,tam:integer;
begin
clrscr;
den:=0;
for i:=1 to n do
begin
xuat(i);
k:=false;
if i=n then
begin
for j:=1 to den do
if b[j]=1 then k:=true;
end
else
for l:=1 to den do
if b[l]=i+1 then k:=true;
if k=false then break;
den:=0;
end;
if k=true then
begin
write('Cac gian hang thong nhau');
readln;
exit;
end
else
begin
writeln('Cac gian hang khong thong nhau');
read(t);
xuat(t);
for i:=1 to den-1 do
for j:=i+1 to den do
if b[i]>b[j] then
begin
tam:=b[i];
b[i]:=b[j];
b[j]:=tam;
end;
for i:=1 to den do
write(b[i],' ');
readln;
end;
readln;
end;
{--------------------------------------------------------}
begin
nhap;
xuli;
end.

Ai có cách gì khác thì chia sẻ cho mọi người với nha! :)

[HGMinh95]

Bạn có thể dùng warshall để bao đóng đồ thị như sau:


Uses crt;
var a:array[1..100,1..100] of boolean;
i,n,t:byte;
procdure Enter;
var f:text;
i,j,b:byte;
begin
assign(f,'hoicho.inp');
reset(f);
readln(f,n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(f,b);
if b=1 then a[i,j]:=true else a[i,j]:=false;
end;
readln(f);
end;
for i:=1 to n do a[i,i]:=true;
close(f);
end;
procedure Warshall;
var k,u,v:byte;
begin
for k:=1 to n do
for u:=1 to n do
for v:=1 to n do
a[u,v]:=a[u,v] or (a[u,k] and a[k,v]);
end;
function Test(b:byte;Show:boolean):boolean;
var kt:boolean;
i:byte;
begin
kt:=true;
for i:=1 to n do
if a[b,i] then
if Show then Write(i,' ')
else kt:=false;
Test:=kt;
end;
Begin
Enter;
Warshall;
Clrscr;
kt:=true;
for i:=1 to n do
if not test(i,false) then
begin
kt:=false;
break;
end;
if kt then write(' Cac gian hang trong hoi cho thong nhau ')
else
begin
writeln(' Cac gian hang trong hoi ko thong nhau ');
write(' Nhap t= '); readln(t);
Test(t,true);
end;
readln
end.
Code build ở tiệm net lên chưa check được, mọi người thông cảm nha:)

[Kid_shock1574]

Bạn ơi ví dụ 1 sai rồi kìa phải là
5
0 1 0 0 1
1 0 1 0 0
0 1 0 1 1
0 0 1 0 1
1 0 1 1 0

[QuynhMyDuyen]

@HGMinh95: Cảm ơn anh đã nhắc nhở.
@Kid_shock1574: Ờ, thanks chú em =))