Tin học lập trình c++

[ngô trang]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Đóng cửa sổ màn hình (c++)
Khi làm việc trên máy tính người ta thường mở rất nhiều cửa sổ. Mỗi cửa sổ là một hình chữ nhật bao gồm một số ô vuông nhỏ kích thước 1 x 1. Một cửa sổ mới được mở, phụ thuộc vào vị trí và kích thước của nó, có thể che khuất một phần hoặc toàn bộ những cửa sổ mở trước nó. Chúng ta có thể đóng cửa sổ bằng cách nháy chuột vào ô vuông nhỏ ở góc phải trên của cửa sổ, nếu như tại thời điểm đó ta nhìn thấy ô vuông này. Một ô của một cửa số là nhìn thấy được nếu như mỗi cửa số che khuất nó đều đã được đóng.
Yêu cầu: Hãy tính số lượng ít nhất lần nháy chuột để có thể đóng được cửa sổ được mở đầu tiên.
Dữ liệu: vào từ file MCLICK.INP:
- Dòng đầu tiên chứa số nguyên N (1 .. 100), là số cửa sổ.
- Mỗi dòng trong số n dòng tiếp theo chứa 4 số nguyên R1, S1, R2, S2 (1 <= R1 <= R2 <= 10000, 1 <= S1 <= S2 <= 10000) trong đó (R1, S1) là toạ độ màn hình của đỉnh góc trái trên, còn (R2, S2) là toạ độ của đỉnh góc phải dưới của cửa sổ. Các cửa sổ được mở theo trình tự chúng xuất hiện trong file dữ liệu.
Chú ý: hãy tưởng tượng màn hình bao gồm một lưới các ô vuông nhỏ. Các dòng của lưới được đánh số từ trên xuống dưới, các cột được đánh số từ trái qua phải bắt đầu từ 1. Ô ở góc trên trái của màn hình nằm ở dòng 1 cột 1.
Kết quả: ghi ra file MCLICK.OUT: một số nguyên duy nhất là số lần nháy chuột ít nhất cần thực hiện để đóng được cửa sổ đầu tiên.
Ví dụ:
MLICK.INP MCLICK.OUT MCLICK.INP MCLICK.OUT
3 3 3 1
3 1 6 4 3 3 4 4
1 2 4 6 1 1 2 2
2 3 5 5 5 5 6 6
Mọi người ơi giúp mình bài này với !!!

 

[Mark Urich]

bạn chụp lại đề lên đi, viết ntn ko rõ ràng đâu, tôi nhìn input là biết ko chính xác rồi.

 

[Mark Urich]

Gợi ý:
Với 2 cửa sổ bất kì A và B, ta thấy chúng có mối quan hệ như sau:
+ Hoặc A và B ko che khuất nhau (nghĩa là điểm đóng ko bị che khuất), hoặc là chúng che khuất nhau.
+ Khi che khuất nhau, giả sử A bị B che khuất, thì để đóng đc A ta bắt buộc phải đóng B trước đã.
+ quan hệ che khuất là 1 chiều, nghĩa là ko thể có A che khuất B và B cũng che khuất A đc.
+ nếu A bị B che khuất thì chắc chắn B phải mở sau A.
+ nếu A1 bị che khuất bởi A2 bị che khuất bởi A3 ...... bị che khuất bởi An thì ko thể có chuyện An bị che khuất bởi A1 đc (ko thể che khuất vòng tròn xảy ra đc)
Như vậy để đóng đc A, ta bắt buộc phải đóng đc tất cả các cửa sổ che khuất A trước, và để đóng đc các cửa sổ che khuất A này, ta lại phải xét đến các cửa sổ che khuất các cửa sổ này, để đóng chúng, cứ như thế.

Trước hết ta phải biểu diễn đc mối quan hệ này khi cho N cửa sổ cho trước. Thông thường phù hợp nhất là sử dụng đồ thị, ở đây là đồ thị có hướng. B che khuất A thì có 1 cạnh có hướng từ B đến A.
Trước hết, bạn đọc dữ liệu từ file vào, dữ liệu như trên thì lưu trữ = 1 mảng 100 x 4 là phù hợp. N là số phần tử của mảng, thứ tự trong mảng cũng chính là thứ tự cửa sổ như trong file.
Sau đó bạn biểu diễn mối quan hệ giữa các cửa sổ với nhau = đồ thị, như trên thì dùng ma trận (mảng 2 chiều) 100 x 100 là đc trong đó a[i, j] = 0 nếu cửa sổ i và j ko che khuất nhau và = 1 nếu i che khuất j (1 chiều), chú ý là a[i, j] = 1 thì a[j, i] = 0 vì i che khuất j thì j ko che khuất i đc (do chỉ 1 chiều thôi). N x N là kích thước mảng này. (N <= 100). Để biểu diễn như này thì bạn xét lần lượt quan hệ giữa 2 phần tử trong mảng dữ liệu trên, rồi gán kết quả vào mảng đồ thị.
Như vậy là xong phần biểu diễn dữ liệu. Đến phần thuật toán. Thuật toán tức là ta phải mô tả cách làm là ntn. có thể có nhiều cách làm, nhưng cách làm nào bao jờ cũng phụ thuộc vào đặc điểm của dữ liệu. Tôi mô tả 1 cách làm như sau: Ta sẽ xét lần lượt từ cửa sổ lớn nhất đến nhỏ nhất, hay đỉnh lơn nhất N đến đỉnh nhỏ nhất 2 (1 là đỉnh đầu tiên, cửa sổ đầu tiên). Với mỗi đỉnh đc xét, ta tìm xem có tồn tại đường đi đến đỉnh 1 hay ko, nếu có thì ta xóa (gán lại = 0, cũng đồng nghĩa với đóng cửa sổ này hay là 1 lần click chuột) tất cả các cạnh từ đỉnh này, rồi ghi lại (tăng) số đếm lên 1 nữa. Để tìm đường đi đến đỉnh 1, bạn phải tìm đc đi đến tất cả các đỉnh kề với N trước, rồi lại tìm đường đi đến tất cả các đỉnh kề với đỉnh này, cứ như thế, như vậy phù hợp nhất là bạn dùng thuật toán kiểu đệ quy (quay lui chẳng hạn), khi tìm đc đỉnh 1 thì dừng lại, nếu ko tìm đc thì ta lại xét tiếp đỉnh N-1. cứ thế.
Cuối cùng ghi ra file số đếm (cộng thêm với 1) là số click chuột ít nhất để đóng cửa sổ 1.

 

[ngô trang]

cảm ơn anh nhiều ạ !!!

 

[ngô trang]

bạn chụp lại đề lên đi, viết ntn ko rõ ràng đâu, tôi nhìn input là biết ko chính xác rồi.