Bài giảng Phân loại bài toán đồ thị

:= u; D[u] := sv; While dau<=cuoi do Begin u := queue[dau]; inc(dau); For v:=1 to n do If A[u,v] and (D[v]=0) then Begin Inc(cuoi); queue[cuoi] := v; D[v] := sv; End; End; End; Procedure Timsvlt; var i: integer; Begin Sv := 0; fillchar(D, sizeof(d), 0); Fillchar(D,sizeof(D),0); for i:=1 to n do if D[i]=0 then begin inc(sv); BFS(i); end; End; Procedure Inkq; Var i, j: integer; Begin Assign(OutPut,fo); Rewrite(OutPut); writeln(sv); For i:=1 to sv do Begin For j:=1 to N do If D[j]=i then Write(j,' '); Writeln; end; Close(Output); End; BEGIN ReadFile; Timsvlt; Inkq; END. Bài 4: Cho bảng hình chữ nhật chia thành m×n ô vuông đơn vị, mỗi ô vuông có ghi số 0 hoặc 1. Một miền 0 của bảng là tập hợp các ô chung đỉnh chứa số 0. Hãy tính số miền 0 của bảng và diện tích của từng miền 0. Dữ liệu vào từ file văn bản MIEN0.INP Dòng 1: Ghi m, n (1<m, n≤100). M dòng tiếp theo thể hiện bảng số theo thứ tự từ trên xuống dưới, mỗi dòng n số theo thứ tự từ trái qua phải. Kết quả ghi ra file MIEN0.OUT Dòng 1: Ghi số lượng miền 0. Dòng 2: ghi diện tích của các miền 0 Ví dụ : MIEN0.INP MIEN0.OUT 8 10 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 4 1 25 14 9 Const Max = 100; Fi = 'MIEN0.INP'; Fo = 'MIEN0.OUT'; dc: Array[1..8] of integer = ( 0, 1, 1, 1, 0,-1,-1,-1); dd: Array[1..8] of integer = (-1,-1, 0, 1, 1, 1, 0,-1); Var A, D: Array[1..Max,1..Max] of integer; QUEUE : Array[1..Max*Max] of Record d,c : integer; End; DT : Array[1..Max*Max] of Integer; N, M , dau, cuoi, sv : integer; Procedure DocF; Var i,j : integer; Begin Assign(Input,Fi); Reset(Input); Readln(M,N); For i:=1 to M do For j:=1 to N do Read(A[i,j]); Close(Input); End; Procedure BFS(i,j : integer); Var k,dong,cot,u,v : integer; Begin Dau:=1; Cuoi:=1; QUEUE[cuoi].d := i; QUEUE[cuoi].c := j; D[i,j] := sv; DT[SV]:=1; While dau<=cuoi do Begin dong := QUEUE[dau].d; cot := QUEUE[dau].c; inc(dau); For k:=1 to 8 do Begin u := dong + Dd[k]; v := cot + Dc[k]; If (u>0) and (u0) and (v<=N) then If (A[u,v]=0) and (D[u,v]=0) then Begin Inc(cuoi); QUEUE[cuoi].d := u; QUEUE[cuoi].c := v; D[u,v] := sv; Inc(DT[sv]); End; End; End; End; Procedure Timsvlt; var i, j: integer; Begin Sv := 0; fillchar(D, sizeof(d), 0); fillchar(DT, sizeof(DT), 0); Fillchar(D,sizeof(D),0); for i:=1 to m do for j:=1 to n do if (a[i,j]=0) and (D[i,j]=0) then begin inc(sv); BFS(i,j); end; End; Procedure Inkq; Var i: integer; Begin Assign(OutPut,fo); Rewrite(OutPut); writeln(sv); For i:=1 to sv do Write(DT[i],' '); Close(Output); End; BEGIN DocF; Timsvlt; Inkq; END. Bài 5: Một lâu đài được chia thành m×n modul vuông (1<m, n<=50). Mỗi modul vuông có từ 0 đến 4 bức tường. Hãy viết chương trình tính : 1 - Lâu đài có bao nhiêu phòng ? 2 - Diện tích phòng lớn nhất là bao nhiêu ? 3 - Bức tường nào cần loại bỏ để phòng càng rộng càng tốt ? Dữ liệu vào từ tệp văn bản LAUDAI.INP Dòng 1: ghi số lượng các môdul theo hướng Bắc-Nam và số lượng các modul theo hướng Đông Tây. Trong các dòng tiếp theo, mỗi modul được mô tả bởi 1 số (0 £p£15). Số đó là tổng của : 1 (= tường phía Tây ), 2 (=tường phía Bắc ) ,4 (=tường phía Đông ) , 8 ( = tường phía Nam) . Các bức tường ở bên trong được xác định hai lần ; bức tường phía Nam trong modul (1,1) đồng thời là bức tường phía Bắc trong modul (2,1) Kết quả ghi ra tệp văn bản LAUDAI.OUT Dòng 1: ghi số lượng phòng. Dòng 2: ghi diện tích của phòng lớn nhất (tính theo số modul ) Dòng 3: ghi bức tường cần loại bỏ (trước tiên là hàng sau đó là cột của modul có tường đó ) và dòng cuối cùng là hướng của bức tường . Ví dụ: 1 2 3 4 5 6 7 N (Bắc) ® 1 W (Tây) E (Đông) 2 3 S (Nam) 4 Mũi tên chỉ bức tường cần loại bỏ theo kết quả ở ví dụ Const NMax = 50; Fi = 'LAUDAI.INP'; Fo = 'LAUDAI.OUT'; dd: Array[0..3] of integer = ( 0,-1, 0, 1); dc: Array[0..3] of integer = (-1, 0, 1, 0); h: array[0..3] of char=('W','N', 'E', 'S'); Var A, D: Array[1..NMax,1..NMax] of integer; queue : Array[1..NMax*NMax] of Record d,c : integer; End; DT : Array[1..NMax*NMax] of Integer; N, M, dau, cuoi, sp, MaxDT, i0, j0, k0: integer; Procedure DocF; Var i,j : integer; Begin Assign(Input,Fi); Reset(Input); Readln(M,N); For i:=1 to M do For j:=1 to N do Read(A[i,j]); Close(Input); End; Procedure BFS(i,j : integer); Var k,dong,cot,u,v : integer; Begin Dau:=1; Cuoi:=1; queue[cuoi].d := i; queue[cuoi].c := j; D[i,j] := sp; DT[sp]:=1; While dau<=cuoi do Begin dong := queue[dau].d; cot := queue[dau].c; inc(dau); For k:=0 to 3 do Begin u := dong + Dd[k]; v := cot + Dc[k]; If (u>0) and (u0) and (v<=N) then If ((A[dong,cot] shr k) and 1 =0) and (D[u,v]=0) then Begin Inc(cuoi); queue[cuoi].d := u; queue[cuoi].c := v; D[u,v] := sp; Inc(DT[sp]); End; End; End; End; procedure TimDtMax; var i: integer; begin MaxDT:=0; for i:=1 to sp do if MaxDT<DT[i] then MaxDT:=DT[i]; end; procedure TimTuong; var i, j, k, max, u, v: integer; begin max:=0; for i:=1 to m-1 do for j:=1 to n-1 do for k:=2 to 3 do begin u:=i+dd[k]; v:=j+dc[k]; if ((a[i,j] shr k) and k =1) and (D[i,j]D[u,v]) then if max < DT[D[i,j]]+DT[D[u,v]] then begin max:=DT[D[i,j]]+DT[D[u,v]]; i0:=i; j0:=j; k0:=k; end; end; end; Procedure Timsvlt; var i, j: integer; Begin sp := 0; fillchar(DT, sizeof(DT), 0); Fillchar(D,sizeof(D),0); for i:=1 to m do for j:=1 to n do if D[i,j]=0 then begin inc(sp); BFS(i,j); end; End; Procedure Inkq; Var i: integer; Begin Assign(OutPut,fo); Rewrite(OutPut); writeln(sp); Writeln(MaxDT); writeln(i0,' ', j0, ' ', h[k0]); Close(Output); End; BEGIN DocF; Timsvlt; TimDtMax; TimTuong; Inkq; END. Bài 6: Cho một lưới hình chữ nhật kích thước m´n gồm các ô vuông đơn vị, mỗi ô được tô 1 trong 6 màu ký hiệu màu 1 , màu 2 màu 6. Giả thiết màu của 2 ô trái trên và phải dưới là khác nhau. Hai ô chung cạnh cùng thuộc một miền nếu cùng màu . Người A đứng ở miền có chứa ô góc trái trên, người B đứng ở miền có chứa ô phải dưới . Hai người chơi lần lượt, đến lượt mình người chơi có thể tô lại màu của miền mà mình đang đứng. Trò chơi kết thúc khi hai người đứng ở hai miền cạnh nhau (chung nhau ít nhất một cạnh của một ô vuông). Tính số lượt đi ít nhất để trò chơi đó kết thúc. Giới hạn: 1 ≤ m, n ≤ 100. Số lượng miền ≤ 100. Dữ liệu vào từ tệp văn bản DOIMAU.INP: Dòng đầu: ghi hai số m , n. M dòng tiếp theo, số thứ j của dòng j ghi số hiệu màu của ô [i, j]. Kết quả ghi ra tệp văn bản DOIMAU.OUT: ghi 1 số duy nhất là số lượt đi ít nhất để trò chơi kết thúc. Ví dụ: DOIMAU.INP DOIMAU.OUT 4 3 1 2 2 2 2 1 1 4 3 1 3 2 3 Phân tích: + Loang từ ô [1, 1] để tìm số miền (sm) . 1 2 2 2 2 3 4 5 6 4 7 8 + Xây dựng véc tơ V màu của từng miền V= 1 2 3 4 5 6 7 8 1 2 1 1 4 3 3 2 5 1 2 3 4 6 7 8 + Xây dựng đồ thị gồm sm đỉnh, xem một miền là một đỉnh của đồ thị. Giữa hai đỉnh có cạnh nối nếu hai miền đó có chung nhau ít nhất một cạnh của một ô vuông. + Tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh sm Trong thủ tục BFS, tại mỗi bước, ta thăm một đỉnh đầu danh sách (giả sử đỉnh đó là đỉnh u), loại nó ra khỏi danh sách và cho những đỉnh v, chưa “xếp hàng” kề với u xếp hàng thêm vào cuối danh sách, tô màu đỉnh v giống màu đỉnh u, đồng thời cho các đỉnh kề với đỉnh v có màu giống với đỉnh u, chưa xếp “xếp hàng” thêm vào cuối danh sách. {$MODE OBJFPC} Const Max = 100; Fi = 'DOIMAU.INP'; Fo = 'DOIMAU.OUT'; dd: Array[1..4] of integer = ( 0,-1, 0, 1); dc: Array[1..4] of integer = (-1, 0, 1, 0); Var A, B, D: Array[1..Max,1..Max] of integer; Queue : Array[1..Max*Max] of record d, c: integer; end; len: array[1..max] of integer; mau: array[1..max] of integer; N, M, sv : integer; Procedure DocF; Var i,j : integer; Begin Assign(Input,Fi); Reset(Input); Readln(M,N); For i:=1 to M do For j:=1 to N do Read(A[i,j]); fillchar(b, sizeof(b),0); fillchar(mau, sizeof(mau),0); Close(Input); End; Procedure BFS(i,j : integer); Var k,dong,cot,u,v, dau, cuoi: integer; Queue : Array[1..Max*Max] of record d, c: integer; end; Begin Dau:=1; Cuoi:=1; Queue[cuoi].d := i; Queue[cuoi].c := j; D[i,j] := sv; mau[sv]:=a[i,j]; While dau<=cuoi do Begin dong := Queue[dau].d; cot := Queue[dau].c; inc(dau); For k:=1 to 4 do Begin u := dong + Dd[k]; v := cot + Dc[k]; If (u>0) and (u0) and (v<=N) then begin If (a[u,v]=a[i,j])and(D[u,v]=0) then Begin Inc(cuoi); Queue[cuoi].d := u; Queue[cuoi].c := v; D[u,v] := sv; End; if (a[u,v]a[i,j]) and (D[u,v]0) then begin b[d[u,v],sv]:=1; b[sv,d[u,v]]:=1; end; end; End; End; End; Procedure Timsvlt; var i, j: integer; Begin Sv := 0; fillchar(D, sizeof(d), 0); for i:=1 to m do for j:=1 to n do if D[i,j]=0 then begin inc(sv); BFS(i,j); end; End; procedure BFS1; Var k, u, v, dau, cuoi : integer; queue: array[1..max] of integer; Begin Dau:=1; Cuoi:=1; Queue[cuoi]:=1; len[1]:=1; While dau<=cuoi do Begin u:=queue[dau]; inc(dau); For v:=1 to sv do if (b[u,v]=1) and (len[v]=0) then Begin Inc(cuoi); Queue[cuoi]:=v; len[v]:=len[u]+1; mau[v]:=mau[u]; for k:=1 to sv do if (b[v,k]=1)and(mau[k]=mau[u])and(len[k]=0) then begin inc(cuoi); queue[cuoi]:=k; len[k]:=len[v]; end; End; End; End; Procedure Inkq; Var i, j: integer; Begin Assign(OutPut,fo); Rewrite(OutPut); {writeln(sv); For i:=1 to m do begin for j:=1 to n do Write(D[i,j],' '); writeln; end;} write(len[sv]-1); Close(Output); End; BEGIN DocF; Timsvlt; BFS1; Inkq; END.