Content

有一个 \(n\times m\) 的扫雷地图，请判断这个地图是否合法，即对于所有格子，是否满足：

• 对应点的数字周围必须有对应数字个雷
• 空的地方周围没有雷

数据范围：\(1\leqslant n,m\leqslant 100\)。

Solution

我们需要遍历整个地图，如果有雷，就将周围所有的格子全部加 \(1\)，最后再判断是否和原地图完全相同即可。

注意需要考虑越界的问题。

Code

const int dx[8] = {0, 0, -1, 1, -1, 1, -1, 1};
const int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
int n, m, shouldbe[107][107];
char a[107][107];

int main() {
	getint(n), getint(m);
	_for(i, 1, n) {
		scanf("%s", a[i] + 1);
		_for(j, 1, m) {
			if(a[i][j] == '*')
				_for(k, 0, 7) {
					int xx = i + dx[k], yy = j + dy[k];
					if(xx < 1 || xx > n || yy < 1 || yy > m)	continue;
					shouldbe[xx][yy]++; 
				}
		}
	}
	_for(i, 1, n)
		_for(j, 1, m)
			if((a[i][j] == '.' && shouldbe[i][j]) || (isdigit(a[i][j]) && a[i][j] - '0' != shouldbe[i][j]))	return printf("NO"), 0;
	printf("YES");
	return 0;
}