Thuật toán

• Sử dụng BFS để đếm số ô đến được từ tổ

• Nhận xét rằng nếu ~S~ lớn ta có thể bị quá thời gian cho phép, tuy nhiên tọa độ của các vật cản được giới hạn trong ô vuông có tọa độ ~10^3~, khi đó hình vuông có tọa độ trái trên là ~(-1001, 1001)~ và phải dưới ~(1001, -1001)~ sẽ chứa tất cả vật cản, gọi số bước từ tổ đến các ô nằm trên cạnh của hình vuông này là ~kc[i,j]~ khi đó số ô đến được từ ô ~(i, j)~ sẽ là:

  • ~S - kc[i,j]~ nếu ~(i, j)~ nằm trên cạnh của hình vuông trên
  • ~(S - kc[i,j] + 1) * (S - kc[i,j] + 2) / 2 - 1~ nếu ~(i, j)~ nằm ở góc của hình vuông

• Vì mảng không lưu được chỉ số âm nên ta có thể tịnh tiến tọa độ của tất cả các ô lên ~1001~. Trong quá trình BFS ta chỉ BFS đã đến đủ ~S~ bước hoặc BFS đến các ô nằm trong giới hạn ~2002~.