주어진 맵에서 각 벽마다 벽을 부쉈을 때 그 벽으로부터 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 각각 구하는 문제입니다. 단순 BFS 또는 DFS를 사용해서 각 벽마다 빈 칸을 구하려면 최악의 경우 $O((NM)^2)$의 시간복잡도까지 나올 수 있습니다. 그런데 N과 M의 값이 최대 1000이므로 시간 초과가 나올 것 같습니다. 그러므로 $O(NM)$에 해결을 해야 합니다. 이 방법으로 생각한 것이 빈 칸마다 그룹을 지정하고, 각 그룹 별 크기를 저장하는 것입니다. 그러면 모든 벽마다 그래프 탐색을 할 필요 없이 바로 옆 칸의 그룹 값을 찾아 그 크기를 모두 더하면 됩니다. 물론 중복해서 더하면 안되기 때문에 중복 체크도 해줘야 합니다. 그런 후 출력 형식에 맞게 맵을 변형시켜 답을 출력하면 됩니다.
PS알못 OrbitHv의 PS