bài giải MTNTRAI spoj THPTCBT – 21697. Nông Trại
các bạn có thể nộp bài trên hệ thống SPOJ THPTCBT tại đây: http://www.spoj.com/THPTCBT/problems/MTNTRAI/ 1. Đề bài MTNTRAI spoj Trong trại chăn nuôi của John có nuôi một số con gà. Trong khi John đang ngủ say, những con cáo đói đã vào trại và tấn công đàn gà. Trại có dạng ...
các bạn có thể nộp bài trên hệ thống SPOJ THPTCBT tại đây: http://www.spoj.com/THPTCBT/problems/MTNTRAI/
1. Đề bài MTNTRAI spoj
Trong trại chăn nuôi của John có nuôi một số con gà. Trong khi John đang ngủ say, những con cáo đói đã vào trại và tấn công đàn gà.
Trại có dạng hình chữ nhật gồm các ô được đánh số bởi hàng và cột. Mỗi ô chứa một kí tự : kí tự “.” là ô trống, kí tự „#‟ là hàng rào, kí tự “c” là gà, kí tự “f” là cáo. Chúng ta coi 2 ô là cùng một chuồng nếu có thể di chuyển từ ô nọ sang ô kia bằng đường đi chỉ gồm các đường theo hàng ngang hoặc thẳng đứng mà không bị vướng vào hàng rào. May thay, những con gà cũng biết tự vệ. Chúng có thể mổ chết những con cáo trong chuồng nếu số lượng gà lớn hơn số lượng cáo trong cùng chuồng. Ngược lại, những con cáo sẽ ăn hết gà trong chuồng đó.
Ban đầu, các con gà và các con cáo đã được xác định trong các miền của trại. Viết chương
trình tính số lượng gà và số lượng cáo còn lại vào sáng hôm sau
Input
– Dòng đầu chứa 2 số nguyên dương m, n là số hàng và số cột của trại (m,n<=1000)
– m dòng tiếp theo, dòng i chứa n kí tự, ký tự thứ j là ký hiệu của ô (i,j) trong trại.
Output
– gồm một dòng duy nhất lần lượt là số cáo và số gà còn lại trong trại.
Example
Input:
8 8
.#######
#..c…#
#.####.#
#.#f.#.#
#.#.c#c#
#c.##..#
#.f..f.#
.######.
Output:
1 3
2. Thuật toán MTNTRAI spoj
Bạn có thể dùng thuật toán BFS hoặc DFS, để duyệt qua các ô liên thông nhau (có thể đi được). trong mỗi vùng liên đó hãy đếm số cáo và gà, cập nhật kết quả bài toán. thực hiện cho đến khi không còn vùng liên thông nào có thể đi chưa duyệt cả.
3. Code tham khảo MTNTRAI spoj
Bạn có thể tham khảo 2 code dưới đây:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | const fi='; fo='; cld:array[1..4] of shortint=(0,-1,0,1); clc:array[1..4] of shortint=(-1,0,1,0); nmax=1000+1; type matran=array[0..nmax,0..nmax] of char; var a:matran; m,n:word; f:text; g,c,ga,cao:longint; procedure docfile; var i,j:word; begin assign(f,fi); reset(f); readln(f,m,n); for i:=0 to m+1 do begin A[i,0]:='#'; a[i,n+1]:='#'; end; for i:=0 to n+1 do begin a[0,i]:='#'; a[m+1,i]:='#'; end; for i:=1 to m do begin for j:=1 to n do read(f,a[i,j]); readln(f); end; close(f); end; procedure DFS(u,v:word); var i:word; x,y:word; begin if a[u,v]='f' then inc(c) else if a[u,v]='c' then inc(g); a[u,v]:='#'; for i:=1 to 4 do begin x:=u+cld[i]; y:=v+clc[i]; if (a[x,y]<>'#') then dfs(x,y); end; end; procedure xuli; var i,j:word; begin ga:=0; cao:=0; for i:=1 to m do for j:=1 to n do if a[i,j]<>'#' then begin g:=0; c:=0; dfs(i,j); if g>c then inc(ga,g) else inc(cao,c); end; assign(f,fo); rewrite(f); writeln(f,cao,' ',ga); close(f); end; begin docfile; end. |
code 2:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | const fii='; foo='; var m,n,u,v,cao,ga: longint; a : array[0..1001,0..1001] of string[1]; ca : array[0..1001,0..1001] of boolean; procedure doc; var i,j : longint; begin assign(input,fii);reset(input); assign(output,foo);rewrite(output); readln(m,n); for i:=1 to m do begin for j:=1 to n do read(a[i][j]); readln(input); end; end; procedure loang(x,y : longint); var i,j : longint; begin if (x<1) or (y<1) or (x>m) or (y>n) then exit; if not ca[x][y] then exit; if (a[x][y]='#') then exit; ca[x][y]:=false; if (a[x][y]='c') then inc(u); if (a[x][y]='f') then inc(v); loang(x-1,y); loang(x+1,y); loang(x,y-1); loang(x,y+1); end; procedure main; var i,j : longint; begin fillchar(ca,sizeof(ca),true); cao:=0;ga:=0; for i:=1 to m do for j:=1 to n do if (a[i][j]='c') or (a[i][j]='f') then if ca[i][j] then begin u:=0; v:=0; //if a[i][j]='c' then inc(u) else inc(v); loang(i,j); if (u>v) then ga:=ga+u else cao:=cao+v; end; writeln(cao,' ',ga); end; begin doc; main; end. |
