Editorial for Bedao Testing Contest 01 - MINE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Bài này có thể nhiều bạn sẽ in ra ma trận đối xứng. Thế nhưng thuật toán đó sai trong trường hợp ma trận input là ma trận đối xứng ở tất cả các phía (và sự thực input toàn là ma trận như thế). Vậy nên chúng ta phải có một thuật toán khác.

Giả sử với bãi mìn sau:

Tổng các số trên những ô không có mìn là 25. Bạn có thể thấy mỗi một đơn vị trong tổng 25 đó thể hiện ~1~ quan hệ ~1~ ô trống và ~1~ ô bom đứng cạnh nhau. Và khi chúng ta đổi ~0~ thành ~1~, ~1~ thành ~0~ thì số lượng các mối quan hệ đó vẫn giữ nguyên không thay đổi.

=> Bài này chỉ cần đảo ~0~ thành ~1~, ~1~ thành ~0~ thì sẽ tạo được một ma trận khác với ma trận ban đầu nhưng tổng số trên những ô không mìn vẫn giữ nguyên.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.