02/10/2018, 14:58
VBGRASS spoj – Bãi cỏ ngon nhất
Nguồn đề bài: http://vn.spoj.com/problems/VBGRASS/ 1. Đề bài VBGRASS spoj Bessie dự định cả ngày sẽ nhai cỏ xuân và ngắm nhìn cảnh xuân trên cánh đồng của nông dân John, cánh đồng này được chia thành các ô vuông nhỏ với R (1 <= R <= 100) hàng và C (1 <= C <= 100) cột. ...
Nguồn đề bài: http://vn.spoj.com/problems/VBGRASS/
1. Đề bài VBGRASS spoj
Bessie dự định cả ngày sẽ nhai cỏ xuân và ngắm nhìn cảnh xuân trên cánh đồng của nông dân John, cánh đồng này được chia thành các ô vuông nhỏ với R (1 <= R <= 100) hàng và C (1 <= C <= 100) cột. Bessie ước gì có thể đếm được số khóm cỏ trên cánh đồng.
Mỗi khóm cỏ trên bản đồ được đánh dấu bằng một ký tự ‘#‘ hoặc là 2 ký tự ‘#’ nằm kề nhau (trên đường chéo thì không phải). Cho bản đồ của cánh đồng, hãy nói cho Bessie biết có bao nhiêu khóm cỏ trên cánh đồng.
Ví dụ như cánh đồng dưới dây với R=5 và C=6:
.#....
..#...
..#..#
...##.
.#....
1 2 3 4 5 | .#.... ..#... ..#..# ...##. .#.... |
Cánh đồng này có 5 khóm cỏ: một khóm ở hàng đầu tiên, một khóm tạo bởi hàng thứ 2 và thứ 3 ở cột thứ 2, một khóm là 1 ký tự nằm riêng rẽ ở hàng 3, một khóm tạo bởi cột thứ 4 và thứ 5 ở hàng 4, và một khóm cuối cùng ở hàng 5.
Dữ liệu
- Dòng 1: 2 số nguyên cách nhau bởi dấu cách: R và C
- Dòng 2..R+1: Dòng i+1 mô tả hàng i của cánh đồng với C ký tự, các ký tự là ‘#’ hoặc ‘.’ .
Kết quả
- Dòng 1: Một số nguyên cho biết số lượng khóm cỏ trên cánh đồng.
Ví dụ
Dữ liệu
.#....
..#...
..#..#
...##.
.#....
1 2 3 4 5 | .#.... ..#... ..#..# ...##. .#.... |
Kết quả
5
1 | 5 |
2. Code tham khảo VBGRASS spoj
a. Code c++
#include <bits/stdc++.h>
#define oo 10000007
#define fto(i, x, y) for (int i = (x); i < (y); ++i)
#define fdto(i, x, y) for (int i = (x); i > (y); --i)
#define maxN 10005
using namespace std;
int r, c, ans = 0;
string a[maxN];
void check(int i, int j) {
a[i][j] = '.';
if (i < r && a[i + 1][j] == '#') check(i + 1, j);
if (j < c && a[i][j + 1] == '#') check(i, j + 1);
if (i > 0 && a[i - 1][j] == '#') check(i - 1, j);
if (j > 0 && a[i][j - 1] == '#') check(i, j - 1);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("vbgrass.inp", "r", stdin);
freopen("vbgrass.out", "w", stdout);
#endif // ONLINE_JUDGE
scanf("%d%d
", &r, &c);
fto (i, 0, r) getline(cin, a[i]);
fto (i, 0, r) {
fto (j, 0, c) {
if (a[i][j] == '#') {
check(i, j);
++ans;
}
}
}
printf("%d", ans);
return 0;
}
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 | #include <bits/stdc++.h> #define oo 10000007 #define fto(i, x, y) for (int i = (x); i < (y); ++i) #define fdto(i, x, y) for (int i = (x); i > (y); --i) #define maxN 10005 using namespace std; int r, c, ans = 0; string a[maxN]; void check(int i, int j) { a[i][j] = '.'; if (i < r && a[i + 1][j] == '#') check(i + 1, j); if (j < c && a[i][j + 1] == '#') check(i, j + 1); if (i > 0 && a[i - 1][j] == '#') check(i - 1, j); if (j > 0 && a[i][j - 1] == '#') check(i, j - 1); } int main() { #ifndef ONLINE_JUDGE freopen("vbgrass.inp", "r", stdin); freopen("vbgrass.out", "w", stdout); #endif // ONLINE_JUDGE scanf("%d%d
", &r, &c); fto (i, 0, r) getline(cin, a[i]); fto (i, 0, r) { fto (j, 0, c) { if (a[i][j] == '#') { check(i, j); ++ans; } } } printf("%d", ans); return 0; } |
b. Code c++
program VBGRASS;
const fi=';
nmax=101;
cld:array[1..4] of shortint=(0,0,-1,1);
clc:array[1..4] of shortint=(-1,1,0,0);
type matran=array[0..nmax,0..nmax] of char;
var m,n:byte;
a:matran;
f:text;
visit:array[1..nmax,1..nmax] of boolean;
s:word;
procedure docfile;
var i,j:byte;
begin
assign(f,fi);
reset(f);
readln(f,m,n);
for i:=1 to m do
begin
for j:=1 to n do
read(f,a[i,j]);
if eoln(f) then
readln(f);
end;
close(f);
end;
procedure DFS(u,v:byte);
var i:byte;
u1,v1:shortint;
begin
visit[u,v]:=true;
for i:=1 to 4 do
begin
u1:=u+cld[i];
v1:=v+clc[i];
if (a[u1,v1]='#')
and (not visit[u1,v1]) then
DFS(u1,v1);
end;
end;
procedure init;
begin
fillchar(visit,sizeof(visit),false);
s:=0;
end;
procedure xuli;
var i,j:byte;
begin
init;
for i:=1 to m do
for j:=1 to n do
if (a[i,j]='#') and (not visit[i,j]) then
begin
DFS(i,j);
inc(s);
end;
writeln(s);
end;
begin
docfile;
xuli;
end.
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 | program VBGRASS; const fi='; nmax=101; cld:array[1..4] of shortint=(0,0,-1,1); clc:array[1..4] of shortint=(-1,1,0,0); type matran=array[0..nmax,0..nmax] of char; var m,n:byte; a:matran; f:text; visit:array[1..nmax,1..nmax] of boolean; s:word; procedure docfile; var i,j:byte; begin assign(f,fi); reset(f); readln(f,m,n); for i:=1 to m do begin for j:=1 to n do read(f,a[i,j]); if eoln(f) then readln(f); end; close(f); end; procedure DFS(u,v:byte); var i:byte; u1,v1:shortint; begin visit[u,v]:=true; for i:=1 to 4 do begin u1:=u+cld[i]; v1:=v+clc[i]; if (a[u1,v1]='#') and (not visit[u1,v1]) then DFS(u1,v1); end; end; procedure init; begin fillchar(visit,sizeof(visit),false); s:=0; end; procedure xuli; var i,j:byte; begin init; for i:=1 to m do for j:=1 to n do if (a[i,j]='#') and (not visit[i,j]) then begin DFS(i,j); inc(s); end; writeln(s); end; begin docfile; xuli; end. |
