Subtask 1

Đáp án sẽ là khoảng cách ~manhattan ~ từ điểm ~S~ tới điểm ~T~.

Subtask 2

Do ~r=0~ nên ta có thể coi các ô có ~c(i,j) = +~ như một ô ~*~, sau đó sử dụng ~BFS~ để tìm đường đi ngắn nhất từ ~S~ tới ~T~.

Subtask 3

Với mỗi ô ~c(i,j) = +~, ta sẽ sử dụng ~BFS~ để đánh dấu các ô bị ảnh hưởng bới nó.

Sau đó, sử dụng ~BFS~ để tìm đường đi ngắn nhất từ ~S~ tới ~T~, không đi qua các ô ~*~ và các ô bị ảnh hưởng bởi bom.

Subtask 4

Thay vì với mỗi ô ~(i,j)~ thỏa mãn ~c(i,j) = +~ ta lại ~BFS~ một lần để tìm các ô bị ảnh hưởng, ta có thể chỉ ~BFS~ một lần bằng cách đưa các ô ~(i,j)~ đó vào ~queue~ luôn từ đầu. Sau đó ta vẫn ~BFS~ như bình thường, kết quả thu được sẽ không thay đổi. Đây gọi là kỹ thuật ~multi-source~.

Sau đó làm tương tự ~subtask~ ~3~.