포탑 부수기

N×M 격자가 있고, 모든 위치에는 포탑이 존재합니다. (즉, 포탑의 개수는 NM개)

각 포탑에는 공격력이 존재하며, 상황에 따라 공격력이 줄어들거나 늘어날 수 있습니다. 또한, 공격력이 0 이하가 된다면, 해당 포탑은 부서지며 더 이상의 공격을 할 수 없습니다. 최초에 공격력이 0인 포탑 즉, 부서진 포탑이 존재할 수 있습니다.

아래와 같은 4×4 크기의 격자를 생각해보겠습니다. (1, 1), (2, 2), (3, 2) 를 포함한 총 7개의 칸은 이미 부서진 포탑을 의미합니다.