지뢰찾기

어느 날 Alex는 컴퓨터의 성능이 그다지 뛰어나지 않았고 많은 사람이 기본으로 제공되는 게임만 하던 어린 시절을 떠올리기로 했다. 당시 Alex는 지뢰찾기를 즐겼다. 그는 테러리스트들이 설치한 폭탄으로부터 자신이 세계를 구한다고 상상했지만, 이기는 일은 드물었다.

그 후 Alex는 성장했고, 이제는 가장 어려운 난이도에서도 쉽게 이긴다. 그는 금세 지루해졌고, 어린 시절 컴퓨터가 잘못된 게임판을 주었으며 그 때문에 자신이 이길 수 없었던 것은 아닐까 생각했다.

이를 확인하려면 여러분의 도움이 필요하다.

A Minesweeper 게임판은 n × m 크기의 직사각형이며, 각 칸은 비어 있거나, 1부터 8까지의 숫자가 있거나, 폭탄이 있다. 모든 칸에 대해 다음 조건을 만족하면 게임판은 올바르다.

• 칸에 숫자 k가 있다면, 인접한 칸 중 정확히 k개에 폭탄이 있다.
• 칸이 비어 있다면, 인접한 모든 칸에 폭탄이 없다.

두 칸이 한 변이나 한 꼭짓점을 공유하면 서로 인접한다(즉, 한 칸에는 인접한 칸이 최대 8개 있다).

첫째 줄에 게임판의 크기를 나타내는 두 정수 n와 m (1 ≤ n, m ≤ 100)이 주어진다.

다음 n개의 줄에 게임판의 설명이 주어진다. 각 줄에는 m개의 문자가 있으며, 각 문자는 "."(이 칸이 비어 있는 경우), "*"(이 칸에 폭탄이 있는 경우), 또는 1 이상 8 이하의 숫자이다.

게임판이 올바르면 "YES"를, 그렇지 않으면 "NO"를 출력한다.

각 문자의 대소문자는 임의로 선택할 수 있다.

두 번째 예제에서 답은 "NO"이다. 폭탄의 위치를 그대로 유지한다면 게임판의 첫째 줄은 21이어야 하기 때문이다.

지뢰찾기에 관한 자세한 내용은 Wikipedia 문서에서 읽을 수 있다.