Giải hộ bài toán pascal cho em với

[amida]

lão amida chắc là bên toán tin hả

Không toán cũng không tin. Năm nay bỏ nghề rồi

[bilun167]

Cách của truongngocdai mình chưa hiểu lắm.
Thật ra mọi người dùng những thuật toán ... cao cấp quá, ko cần thiết.
Nhận xét: Nếu xét từ trên xuống dưới, từ trái qua phải
_ Nếu ô [i,j] nào đó có xe tăng thì chắc chắn bomb nó.
_ Nếu ô [i,j] ko có xe tăng thì xét [i,j+1] và [i+1,j], nếu 2 ô này ĐỀU có xe tăng thì bomb vào ô [i,j] (để kill cùng lúc 2 đứa).
Sau mỗi lần bomb đương nhiên fải cập nhật lại giá trị cho [i,j] [i,j+1] [i+1,j] [i+1,j+1] về 0 hén. Còn xuất toạ độ thì dễ rồi, bomb ở đâu thì lưu toạ độ ở đó, in ra.
Độ fức tạp O(n^2). Theo bài này n đủ nhỏ để chấp nhận rùi.

[tastsuka]

cách đó chỉ đảm bảo diệt hết xe chứ bom thì phung phí kinh khủng làm sao thỏa mãn dc

[bilun167]

@tastsuka: bảo đảm ít nhất, ko tin thì bạn đọc lại đi.
Mà để mình nói rõ ở đây luôn:
Đầu tiên quan trọng nhất là XÉT TỪ TRÊN XUỐNG và TỪ TRÁI QUA PHẢI.
Nếu ở [i,j] có tăng mà ko bomb thì còn cơ hội nào để bomb nó nữa
Nếu ở [i,j] ko có tăng thì chỉ bomb khi nó có thể kill nhiều tăng hơn những [i',j'] khác, ở đây kill đc 2 thằng trở lên là đc rùi (1 thằng bên fải, 1 thằng ở dưới) {còn ô [i+1,j+1] có tăng hay ko cũng kệ}
Nếu quét theo trình tự trên mình khẳng định đây là cách tiết kiệm bomb nhất, nếu bạn ko tin thì cứ thử tìm test sai đi

[bete]

Thân gửi bạn bilun167:

Cho tui thắc mắc 1 chút:

Nhận xét: Nếu xét từ trên xuống dưới, từ trái qua phải
_ Nếu ô [i,j] nào đó có xe tăng thì chắc chắn bomb nó.
_ Nếu ô [i,j] ko có xe tăng thì xét [i,j+1] và [i+1,j], nếu 2 ô này ĐỀU có xe tăng thì bomb vào ô [i,j] (để kill cùng lúc 2 đứa).

Giả sử mình có (1: có xe tăng; 0: không có xe tăng)
111
010

=> cách của bạn sẽ đặt bom đầu tiên ở [1,1] (màu dỏ) ???

111
010

=> sẽ tốn 2 trái bom tất cả:
111
010

Trong khi chỉ cần tốn có 1 trái bom mà thôi
111
010

(hiểu biết nông cạn, có gì sai sót mong được góp ý, xin cám ơn)

-thân

[bilun167]

trời ui, đề bài có cho fép đặt bom ở [i,j] mà fá huỷ đc tăng (nếu có) ở ô [i,j-1] đâu hả bạn. chính vì thế mình mới nói thuật của mình duyệt từ trên xuống dưới & từ trái wa fải là vì mục đích [i,j-1] ko thể bị fá huỷ khi đặt bomb ở [i,j] đấy chứ
mình nói ko sai chứ?

[bete]

Thân gửi bạn bilun167,

Xin thành thực xin lỗi: cái ví dụ của tui là sai rồi (lúc đó tui đang nghĩ tới 1 bài tương tự)

Nếu ô [i,j] ko có xe tăng thì xét [i,j+1] và [i+1,j], nếu 2 ô này ĐỀU có xe tăng thì bomb vào ô [i,j] (để kill cùng lúc 2 đứa).

=> tui xin thắc mắc 1 chút nghen:

Giả sử mình có (1: có xe tăng; 0: không có xe tăng):

011
100
100

=> cách của bạn sẽ đặt bom đầu tiên ở [1,1] (màu dỏ) ???
011
100
100

=> sẽ tốn 3 trái bom tất cả:
011
100
100

Trong khi chỉ cần tốn có 2 trái bom mà thôi
011
100
100

(hiểu biết nông cạn có gì sai sót mong được góp ý, xin cám ơn)

-thân

[bilun167]

Đầu tiên là fải cảm ơn bạn bete nhiều, mình đã sai sót, ko lường đến trường hợp này.
Thứ hai mình xin bổ sung thêm thuật giải của mình: nếu ô [i,j] ko có tăng thì chỉ đánh bomb khi 3 ô xung wanh ko có ô nào bomb "tốt" hơn nó. Lưu ý với 3 ô xung wanh thì chỉ xét ô cạnh fải và bên dưới nó thôi chứ ko cần xét với ô chéo góc.
Mong mọi người tiếp tục góp ý

[bete]

Thân gửi bạn bilun167,

nếu ô [i,j] ko có tăng thì chỉ đánh bomb khi 3 ô xung wanh ko có ô nào bomb "tốt" hơn nó. Lưu ý với 3 ô xung wanh thì chỉ xét ô cạnh fải và bên dưới nó thôi chứ ko cần xét với ô chéo góc.

=> tui xin có chút thắc mắc:

1) có phải ý của bạn là nếu ô [i,j] ko có xe tăng thì xét 3 ô [i,j+1], [i+1,j] và [i+1,j+1] ?

2) Và nếu xét 3 ô này thì xét ra sao ? Xét tới độ sâu cỡ nào ? Độ sâu bằng 1 có nghĩa là chỉ xét các ô kế cận 3 ô chung quanh này ? Độ sâu bằng 2 có nghĩa là xét thêm các ô kế cận các ô kế cận 3 ô chung quanh này; ....

3) Và khi xét thì không cần xét ô chéo góc co nghĩa là không cần xét [i+1,j+2],[i+2,j+1] và [i+2,j+2] ? Bạn có thể nói tại sao lại như vậy hay không ?

(hiểu biết nông cạn; có gì sai sót mong được góp ý, xin cám ơn)

-thân

[bilun167]

1. Xét ở [i,j] và vấn đề ở đây chỉ còn là [i,j] ko có tăng thì bomb thế nào.
Bomb ở [i,j] <=> ở [i,j] (thật ra [i,j] ko có tăng rồi, nói ra cho dễ hình dung thôi),[i+1,j],[i,j+1] (gọi là vùng xét đi cho tiện) có tối thiểu 2 ô có tăng và ở các ô [i+1,j], [i,j+1] có vùng xét với tổng số tăng (ko tính tăng trùng nhau nha bạn) ít hơn số tăng trong vùng xét của [i,j].
Note: Vùng xét của [i+1,j] là [i+2,j], [i,j+2]. Tương tự với vùng xét của [i,j+1].

2. Sở dĩ ko xét ô [i+1,j+1]khi kiểm tra ô [i,j] (ko có tăng) có bomb hay ko là vì thế này: Ta bomb ở [i,j] (ko có tăng) khi có tối thiểu 2 ô trong vùng xét có bomb, sẽ có 2 trường hợp:
_ Nếu [i+1,j] và [i,j+1] đều có bomb thì ta xét 2 ô fải và dưới xem tổng các tăng trong vùng xét của nó có >= số tăng trong vùng xét của [i,j] ko, nếu ko thì bomb.
_ Còn tại sao ko wan tâm đến [i+1,j+1] là vì thế này: khi [i,j] ko có bomb và trong 3 ô còn lại của vùng xét chỉ có 2 ô có tăng (vì nếu cả 3 ô đều có tăng thì bomb nó rồi). Nếu 2 ô này là [i,j+1] và [i+1,j+1] thì có fải ta nên bomb ở [i,j+1] sẽ có cơ may kill đc nhiều hơn đúng ko? Tương tự với cặp [i+1,j] và [i+1,j+1].