Bài toán táo rơi

#1

ai cho mình xin ý tưởng về bài này được ko

Bạn có một bức tranh hình chữ nhật có kích cỡ m × n. Bức tranh này được chia thành m × n ô vuông bằng nhau, mỗi ô sẽ là một ô trống, hoặc là một quả táo, hoặc là một chướng ngại vật nào đó.

Bạn muốn biết sau khi tất cả các quả táo đã rơi hết xuống mặt đất hoặc chướng ngại vật, bức tranh
cuối cùng sẽ trông như thế nào. Để việc tìm bức tranh cuối cùng trở nên đơn giản, bạn quyết định sử dụng hai định luật sau, gọi là Định luật Táo rơi I và Định luật Táo rơi II:

  • Chướng ngại vật luôn đứng yên.
  • Nếu có một ô trống ở dưới một quả táo, quả táo sẽ di chuyển vào ô trống đó.

Hãy in ra bức tranh cuối cùng sau khi tất cả các quả táo đều đã rơi xong. Lưu ý rằng nếu bạn mô phỏng lại toàn bộ quá trình táo rơi, bạn sẽ không có đủ thời gian.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên dương m và n (1 ≤ m ≤ 50000, 1 ≤ n ≤ 10) cho biết số lượng
    dòng và cột của bức tranh.
  • m dòng tiếp theo, mỗi dòng gồm n kí tự mô tả bức tranh. Các ô trống được mô tả bằng kí tự ’.’,
    các ô chứa quả táo được mô tả bằng kí tự ’a’, các ô chứa chướng ngại vật được mô tả bằng kí tự '#’.

Kết quả

  • Gồm m dòng, mỗi dòng chứa n kí tự mô tả bức tranh cuối cùng sau khi tất cả các quả táo đã rơi
    xong.
#2

một cột có thể chứa nhiều quả táo không? Nếu có, bản thân quả táo có tính là chướng ngại vật không?

#3

Chép đề thì chép luôn ví dụ mẫu.
Đọc đề chả biết táo rơi theo phương, chiều nào? Vị trí bắt đầu rơi?

2 Likes
#4

một cột có thể có nhiều test.
mình có một số vd đây bạn:
-vd1:
input:

3 3
aaa
#..
..#

output:

a..
#.a
.a#

-vd2:
input:

4 5
aaa.a
aa.a.
a.a..
...a.

output:

.....
a....
aaaa.
aaaaa
1 Like
#5

nhầm là táo ko phải là test

#6
  • C1: vớt từng cột, xét vị trí cuối cùng, dò dần lên, gặp táo thì chuyển xuống dưới, gặp chướng ngại vật thì lặp lại quá trình với chướng ngại vật là vị trí cuối cùng
  • C2: Lấy thông tin về các cặp chướng ngại vật của từng cột, đếm số táo giữa 2 chướng ngại vật ngay từ bước input, rồi lắp số táo đã đếm vào ma trận thôi, bài này dễ mà nhỉ
3 Likes
#7

Đề lừa tình nhé :yum:

Bài này mỗi cột là độc lập với cột khác, nên có thể thu nhỏ bài tập về column vector với các chướng ngại vật.

Dựa vào các chướng ngại vật có thể chia column vector thành các array con. Bài được chuyển thành bài dồn 1 phần tử bất kì về đầu/cuối mảng con.

Giải thuật đưa về đầu và cuối mảng thì có 3 giải thuật sort quen thuộc: selection, bubble, insertion. Cái insertion sort là phù hợp nhất.

Ngoài ra còn có giải thuật sử dụng cách đếm là distribution counting sort.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?