Các bài tập lập trình C và giải thuật

[hailoc12]

12.9. Nhà cao tầng
Một quần thể nhà cao tầng được xây dựng trên một nền hình chữ nhật, trên đó đựơc chia thành M*N ô vuông (M dòng, N cột ). Các dòng đựơc đánh số từ 1 đến N. Người ta xem khu nhà được tạo bởi các khối có đáy là một ô vuông với những chiều cao nào đó mà người ta gọi là những đơn nguyên. Một đơn nguyên được xác định bởi toạ độ dòng, cột của ô đáy và chiều cao tương ứng. Một khối nhà được định nghĩa là một tập hợp các đơn nguyên có đáy tạo thành một miền gồm những ô vuông kề cạnh.
Người ta đánh số các khối nhà bằng những số nguyên liên tiếp bắt đầu từ 1 theo trình tự duyệt các ô đáy theo từng dòng từ 1 đến M, và trên mỗi dòng, duyệt các ô đáy theo từng cột từ 1 đến N.
Người ta muốn quét vôi các bức tường xung quanh tất cả các khối nhà. Hãy xác định
* Số lượng các khối nhà
* Tổng diện tích quét vôi
* Khối nhà có diện tích quét vôi lớn nhất và giá trị của diện tích này.
Dữ liêu vào cho trên file văn bản có dạng:
M N
H[1,1] H[1,2].... H[1,N]
H[2,1].....
....
H[M,1]...............H[M,N]
trong đó H[i, j] là chiều cao của đơn nguyên [i, j] với các quy ước bằng 0 khi đơn nguyên này không có. Giải thiết rằng các giá trị này đêềulà những số nguyên và tính theo đơn vị một cạnh ô vuông. Các số trên cùng một dòng ghi cách nhau ít nhất một dấu cách.

Kết quả ghi ra file văn bản gồm:
* Dòng đầu ghi số lượng các khối nhà
* Dòng thứ hai ghi tổng số diện tích quét vôi
* Dòng thứ ba ghi số nhà của khối có diện tích quết vôi lớn nhất và giá trị của diện tích này ( ghi cách nhau ít nhất một dấu cách).
Ví dụ:
Input
4 6
1 2 3 0 2 1
1 0 1 0 0 1
2 1 1 0 0 1
0 0 0 1 1 0

Output
3
50
1 30
Ghi chú:
* Các giá trị diện tích được tính theo đơn vị diện tích một ô vuông
* Giới hạn kích thước: M, N <= 100, H[i, j] <=2000

[rox_rook]

Sau đây là cách giải của anh, áp dụng thuật toán loang :
Ý tưởng là ta xét 4 ô xung quanh 1 ô ví dụ ô H[r][c], vì là 1 đơn nguyên nên 2 ô kế nhau có cùng hàng và cùng cột thì thỏa mãn đề bài. Vậy có thể thấy những ô như :
H[r+1][c]
H[r-1][c]
H[r][c+1]
H[r][c+1]
nếu khác 0 và -1 (viền bảng) thì thỏa mãn, từ đó ta có hàm loang như sau :

void Spreading_Programming (int r, int c , int &s)     {        H[r][c] = 0;         s = s + 4*tmp[r][c]; /*đầu tiên sơn xung quanh bốn bức tường của đơn nguyên*/            /*Bỏ đi cạnh chung của những đơn nguyên cạnh nó, thằng nào thấp hơn thì chọn*/        s = s - min(tmp[r][c],tmp[r][c+1]) - min(tmp[r][c],tmp[r][c-1])                - min(tmp[r][c],tmp[r+1][c]) - min(tmp[r][c],tmp[r-1][c]);                if ( H[r+1][c] != 0 && H[r+1][c] != -1 ) Spreading_Programming (r+1, c, s);         if ( H[r-1][c] != 0 && H[r-1][c] != -1 ) Spreading_Programming (r-1, c, s);        if ( H[r][c+1] != 0 && H[r][c+1] != -1 ) Spreading_Programming (r, c+1, s);          if ( H[r][c+1] != 0 && H[r][c-1] != -1 ) Spreading_Programming (r, c-1, s);  }

Bài này thực ra không khó lắm nhưng chỗ này thì đúng là nhức cả đầu, hồi đầu anh cứ nghĩ là V[sơn] = cột*hàng*cao , debug mãi không ra kết quả. Phải vẽ ra cái hình mới hiểu được

Anh nghĩ chắc đây là cái hay của bài này, không biết có phải không nhỉ ?

Tiếp theo ta cứ loang theo vết của từng ô cho tới khi hết bảng ! Dùng 1 biến max_area để tính khối nhà có diện tích lớn nhất là xong !
Còn 1 chỗ đáng chú ý là :

H[r][c] = 0; /*tránh đi lại những ô đã đi qua, ví du dang xét ô H[1][3], ta kiểm tiếp tra ô [2][3], nhận thấy nó có khối nguyên ô [2][3], tiếp đến ta kiểm tra ô [3][5] thì không có khối nguyên, bỏ qua và quay lại xét sang ô [1][5] thì lại thấy đơn nguyên, loang lại ô [1][5] -> dẫn đến Stack Over Flow */

nhưng vì gán H[r][c] = 0 cho nên khi tính diện tích ta lại mất đi chiều cao vì thế dùng 1 mãng phục tmp[r][c] ( chú ý không có viền cho mãng này ) là xong.

Bài này có 2 vấn đề : 1 là phương pháp loang, 2 là công thức thể tích .

Và sau đây là toàn bộ code :

#include <iostream>#include <fstream>#include <iomanip> #define FI "TOANHA.inp"#define maxx 100  int H[maxx][maxx], tmp[maxx][maxx]; int M, N; /*M represent Row, N represents Colunm*/int building;int max_area;int total_area; void InputData()     {        ifstream F;        F.open(FI);        F >> M >> N;         F.ignore();                for ( int i = 1; i <= M; i++){                for( int j = 1; j <= N; j++){                        F >> H[i][j];                }            F.ignore();        }        F.close();} void Initialization()     {        /*Set range for the area*/        for ( int i = 0; i <= N+1; i++ ){                H[0][i] = -1;                H[M+1][i] = -1;        }              for ( int i = 0; i <= M+1; i++ ){                H[i][0] = -1;                H[i][N+1] = -1;        }        /*Print map*/        for ( int i = 0; i <= M+1; i++ ){                for ( int j = 0; j <= N+1; j++ ){                        cout << H[i][j] << setw(3);                }                cout << endl;        }                /*Sub Array*/        for ( int i = 1; i <= M; i++)        {                for( int j = 1; j <= N; j++ )                {                        tmp[i][j] = H[i][j];                }        }} int min ( int a, int b )        {        if ( a < b ) return a;        else         return b;} void Spreading_Programming (int r, int c , int &s)     {        H[r][c] = 0;                s = s + 4*tmp[r][c]; /*Paint around the building, 4 sides*/            /*Eleminate the share side of 2 building, which ones lower is chosen*/        s = s - min(tmp[r][c],tmp[r][c+1]) - min(tmp[r][c],tmp[r][c-1])                - min(tmp[r][c],tmp[r+1][c]) - min(tmp[r][c],tmp[r-1][c]);                if ( H[r+1][c] != 0 && H[r+1][c] != -1 ) Spreading_Programming (r+1, c, s);         if ( H[r-1][c] != 0 && H[r-1][c] != -1 ) Spreading_Programming (r-1, c, s);        if ( H[r][c+1] != 0 && H[r][c+1] != -1 ) Spreading_Programming (r, c+1, s);          if ( H[r][c+1] != 0 && H[r][c-1] != -1 ) Spreading_Programming (r, c-1, s);  } void Process()     {                int area;        building = 0;        max_area = 0;        total_area = 0;        for ( int i = 1; i <= M; i++)        {                for( int j = 1; j <= N; j++)                {                        if ( H[i][j] != -1 && H[i][j] != 0 ) /*If there's no "don nguyên*/                        {                                area = 0;                                Spreading_Programming ( i, j, area);                                                                building = building + 1; /*Each time increases the number of building*/                                total_area = total_area + area; /*Also increase total area*/                                /*Chose building have maximum area*/                                if ( area > max_area )                                {                                        max_area = area;                                                                        }                        }                }        }}  void OutputData()     {                cout << "There are : " << building << " buildings " << endl;        cout << "Total area is : " << total_area << endl;        cout << "The maximum area is : " << max_area << endl;} void main()     {        InputData();        Initialization();        Process();        OutputData();                cin.get(); }

[buitheanhdb]

Bài của bạn rox_rook còn thiếu một phần đấy là:
bạn mới đếm được số ô vuông là đơn nguyên nhưng không đánh số được các khối nhà (block)
Theo mình thì bài toán có thể giải quyết theo ý tưởng thế này:
Mảng A, kích thước MxN trong đó:
A[i][j] = 0 nếu H[i][j] = 0 (Không có nhà xây trên ô vuông này)
A[i][j] = 1 nếu H[i][j] đã được chọn để tính vào tổng diện tích
A[i][j] = -1 nếu H[i][j] chưa được chọn để tính tổng diện tích

biến BlockCount: lưu số lượng các khối nhà

Sử dụng thuật toán loang như bạn rox_rook giới thiệu:

nếu còn tồn tại A[i][j] = -1
Sử dụng thuật toán loang tại ô A[i][j]
Tính toán tổng diện tích và diện tích Block lớn nhất
Tăng biến BlockCount lên một đơn vị

[rox_rook]

Kết quả ghi ra file văn bản gồm:
* Dòng đầu ghi số lượng các khối nhà
* Dòng thứ hai ghi tổng số diện tích quét vôi
* Dòng thứ ba ghi số nhà của khối có diện tích quết vôi lớn nhất và giá trị của diện tích này ( ghi cách nhau ít nhất một dấu cách).

Bài của bạn rox_rook còn thiếu một phần đấy là:
bạn mới đếm được số ô vuông là đơn nguyên nhưng không đánh số được các khối nhà (block)

Bạn check thử chưa code mình viết chưa nhỉ ?

[rox_rook]

Output
3
50
1 30

Sorry, không thấy đường T_T ! Cám ơn ý kiến của bạn !