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

1.  XCoworker Member Ngày gia nhập
08 2006
Nơi ở
Hải Phòng
Bài viết
218

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

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  Trả lời cùng với trích dẫn

2. 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 :

C++ Code:
1. void Spreading_Programming (int r, int c , int &s)
2.
3.     {
4.         H[r][c] = 0;
5.         s = s + 4*tmp[r][c]; /*đầu tiên sơn xung quanh bốn bức tường của đơn nguyên*/
6.
7.         /*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*/
8.         s = s - min(tmp[r][c],tmp[r][c+1]) - min(tmp[r][c],tmp[r][c-1])
9.               - min(tmp[r][c],tmp[r+1][c]) - min(tmp[r][c],tmp[r-1][c]);
10.
11.         if ( H[r+1][c] != 0 && H[r+1][c] != -1 ) Spreading_Programming (r+1, c, s);
12.         if ( H[r-1][c] != 0 && H[r-1][c] != -1 ) Spreading_Programming (r-1, c, s);
13.         if ( H[r][c+1] != 0 && H[r][c+1] != -1 ) Spreading_Programming (r, c+1, s);
14.         if ( H[r][c+1] != 0 && H[r][c-1] != -1 ) Spreading_Programming (r, c-1, s);
15.
16. }

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, ta kiểm tiếp tra ô , nhận thấy nó có khối nguyên ô , tiếp đến ta kiểm tra ô  thì không có khối nguyên, bỏ qua và quay lại xét sang ô  thì lại thấy đơn nguyên, loang lại ô  -> 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 :

C++ Code:
1. #include <iostream>
2. #include <fstream>
3. #include <iomanip>
4.
5. #define FI "TOANHA.inp"
6. #define maxx 100
7.
8.
9. int H[maxx][maxx], tmp[maxx][maxx];
10. int M, N; /*M represent Row, N represents Colunm*/
11. int building;
12. int max_area;
13. int total_area;
14.
15. void InputData()
16.
17.     {
18.         ifstream F;
19.         F.open(FI);
20.         F >> M >> N;
21.         F.ignore();
22.
23.         for ( int i = 1; i <= M; i++){
24.                 for( int j = 1; j <= N; j++){
25.                         F >> H[i][j];
26.                 }
27.             F.ignore();
28.         }
29.         F.close();
30. }
31.
32. void Initialization()
33.
34.     {
35.         /*Set range for the area*/
36.         for ( int i = 0; i <= N+1; i++ ){
37.                 H[i] = -1;
38.                 H[M+1][i] = -1;
39.         }
40.
41.         for ( int i = 0; i <= M+1; i++ ){
42.                 H[i] = -1;
43.                 H[i][N+1] = -1;
44.         }
45.         /*Print map*/
46.         for ( int i = 0; i <= M+1; i++ ){
47.                 for ( int j = 0; j <= N+1; j++ ){
48.                         cout << H[i][j] << setw(3);
49.                 }
50.                 cout << endl;
51.         }
52.
53.         /*Sub Array*/
54.         for ( int i = 1; i <= M; i++)
55.         {
56.                 for( int j = 1; j <= N; j++ )
57.                 {
58.                         tmp[i][j] = H[i][j];
59.                 }
60.         }
61. }
62.
63. int min ( int a, int b )
64.
65.     {
66.         if ( a < b ) return a;
67.         else         return b;
68. }
69.
70. void Spreading_Programming (int r, int c , int &s)
71.
72.     {
73.         H[r][c] = 0;
74.         s = s + 4*tmp[r][c]; /*Paint around the building, 4 sides*/
75.
76.         /*Eleminate the share side of 2 building, which ones lower is chosen*/
77.         s = s - min(tmp[r][c],tmp[r][c+1]) - min(tmp[r][c],tmp[r][c-1])
78.               - min(tmp[r][c],tmp[r+1][c]) - min(tmp[r][c],tmp[r-1][c]);
79.
80.         if ( H[r+1][c] != 0 && H[r+1][c] != -1 ) Spreading_Programming (r+1, c, s);
81.         if ( H[r-1][c] != 0 && H[r-1][c] != -1 ) Spreading_Programming (r-1, c, s);
82.         if ( H[r][c+1] != 0 && H[r][c+1] != -1 ) Spreading_Programming (r, c+1, s);
83.         if ( H[r][c+1] != 0 && H[r][c-1] != -1 ) Spreading_Programming (r, c-1, s);
84.
85. }
86.
87. void Process()
88.
89.     {
90.
91.         int area;
92.         building = 0;
93.         max_area = 0;
94.         total_area = 0;
95.         for ( int i = 1; i <= M; i++)
96.         {
97.                 for( int j = 1; j <= N; j++)
98.                 {
99.                         if ( H[i][j] != -1 && H[i][j] != 0 ) /*If there's no "don nguyên*/
100.                         {
101.                                 area = 0;
102.                                 Spreading_Programming ( i, j, area);
103.
104.                                 building = building + 1; /*Each time increases the number of building*/
105.                                 total_area = total_area + area; /*Also increase total area*/
106.                                 /*Chose building have maximum area*/
107.                                 if ( area > max_area )
108.                                 {
109.                                         max_area = area;
110.
111.                                 }
112.                         }
113.                 }
114.         }
115. }
116.
117.
118. void OutputData()
119.
120.     {
121.
122.         cout << "There are : " << building << " buildings " << endl;
123.         cout << "Total area is : " << total_area << endl;
124.         cout << "The maximum area is : " << max_area << endl;
125. }
126.
127. void main()
128.
129.     {
130.         InputData();
131.         Initialization();
132.         Process();
133.         OutputData();
134.
135.         cin.get();
136.
137. }
Đã được chỉnh sửa lần cuối bởi rox_rook : 14-10-2007 lúc 02:58 PM.  Trả lời cùng với trích dẫn

3. 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ị  Trả lời cùng với trích dẫn

4. 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ỉ ?   Trả lời cùng với trích dẫn

5. Output
3
50
1 30
Sorry, không thấy đường T_T ! Cám ơn ý kiến của bạn !  Trả lời cùng với trích dẫn

#### Quyền hạn của bạn

• Bạn không thể gửi đề tài mới
• Bạn không thể gửi bài trả lời
• Bạn không thể gửi các đính kèm
• Bạn không thể chỉnh sửa bài viết của bạn