Nhận xét then chốt

Nếu Pegman đi ra khỏi bản đồ thì trước đó phải có một mũi tên chỉ về phía một biên lưới mà không có mũi tên nào khác nằm giữa nó và biên đó. Vì vậy, mọi mũi tên như thế đều phải được đổi để chỉ về phía một mũi tên khác.

Ta chỉ cần đếm số mũi tên đang chỉ theo một hướng không có mũi tên nào khác trước khi tới biên. Nếu có một mũi tên không thể chỉ về bất kỳ mũi tên nào khác — tức là không có mũi tên nào khác trong cả hàng lẫn cột của nó — thì đáp án là IMPOSSIBLE. Nếu không, mỗi mũi tên đang chỉ sai cần đúng một lần đổi, và tổng số mũi tên ấy là đáp án.

Có thể kiểm tra bốn hướng của mỗi mũi tên bằng các lượt quét theo hàng và cột, đạt \(O(RC)\) thời gian và \(O(RC)\) bộ nhớ.

Dựa trên phân tích chính thức của Google Code Jam.