[Lập trình newbie] Mỗi ngày một bài toán (số 11)

[11520473]

trên đường chéo thì không phải

Anh ơi cho em hỏi. Đường chéo là như thế nào ạ. Trong ma trận hình vuông thì mới có đường chéo chứ, còn hình chữ nhật thì xác định đường chéo như thế nào ạ

[09520281]

Anh ơi cho em hỏi. Đường chéo là như thế nào ạ. Trong ma trận hình vuông thì mới có đường chéo chứ, còn hình chữ nhật thì xác định đường chéo như thế nào ạ

Như thế này thì ko phải 1 khóm nè
..#...
...#..

[11520447]

Theo mình như vậy thì có 4 khóm thôi

tức là có khóm sẽ dc đếm 2 lần ?

[11520132]

Đọc các post rồi mà vẫn không hiểu bây giờ tính các khóm sao, # tính rồi có được tính lại không :|

[09520434]

Nếu đề như cũ thì chúng ta nên đếm làm sao cho số khóm cỏ là ít nhất, hay nhiều nhất. ()

Sửa đề tí cho đơn giản. :shy:
...
Mỗi khóm cỏ trên bản đồ được đánh dấu bằng một ký tự ‘#‘ hoặc một nhóm ký tự ‘#’ nằm kề nhau (một ô thuộc nhóm là ô có khả năng đến được một ô khác cũng thuộc nhóm đó chỉ bằng một bước duy nhất : {lên, xuống, trái, phải}) :adore:

#####
OOOOO
#OO##
O#OO#

như thế này thì chúng ta có 4 nhóm.

[quoctinvn]

const
  fi = 'GAMCO.INP';
  fo = 'GAMCO.OUT';
  dx : array[1..4] of longint = (-1,0,1,0);
  dy : array[1..4] of longint = (0,1,0,-1);
  maxN= 100;
type
  pos = record i,j :longint; end;
var
  f1,f2 : text;
  free : array[1..maxN+1,1..maxN+1] of boolean;
  a : array[1..maxN+1,1..maxN+1] of char;
  q : array[1..maxN*maxN+1] of pos;
  n,m,first,last : longint;
procedure openfiles;
begin
  assign(f1,fi); reset(f1);
  assign(f2,fo); rewrite(f2);
end;

procedure closefiles;
begin
  close(f1); close(f2);
end;

procedure init;
var
  i,j : longint;
begin
  readln(f1,n,m);
  for i := 1 to n do
    begin
      for j := 1 to m do read(f1,a[i,j]);
      readln(f1);
    end;
end;

procedure push(i,j : longint);
begin
  inc(last);
  q[last].i := i; q[last].j := j;
end;

function pop : pos;
begin
  pop.i := q[first].i; pop.j := q[first].j;
  inc(first);
end;

procedure bfs(i,j : longint);
var
  k,ii,jj : longint;
  p : pos;
begin
  //Empty queue;
  first := 1; last := 0;
  push(i,j);
  free[i,j] := false;
  repeat
    p := pop;
    for k := 1 to 4 do
      begin
        ii := p.i + dx[k];
        jj := p.j + dy[k];
        if (ii >=1) and (ii <= n) and (jj >= 1) and (jj <=m) and (a[ii,jj] = '#') and free[ii,jj] then
          begin
            free[ii,jj] := false;
            push(ii,jj);
          end;
      end;
  until first>last;
end;

procedure solve;
var
  res,i,j : longint;
begin
  res := 0;
  fillchar(free,sizeof(free),true);
  for i := 1 to n do
    for j := 1 to m do
      if (a[i,j] = '#') and free[i,j] then
        begin
          inc(res);
          bfs(i,j);
        end;
  write(f2,res);
end;

begin
  openfiles;
  init;
  solve;
  closefiles;
end.

Sử dụng thuật BFS ("loang"). Với mỗi vị trí "#" tìm được chưa được đánh dấu, cho vào 1 queue. Từ điểm đó duyệt lần lượt sang 4 hướng lên xuống trái phải. Nếu 1 trong4 hướng này là "#" thì đánh dấu và thêm vào queue và tiếp tục như vậy. Khi duyệt hết queue thì tức là đã đi qua hết 1 bãi cỏ.

[quoctinvn]

có ep 12 chưa ạ :shot: