地雷
题目背景
小埋总是在家中打游戏，一天，她突然想玩Windows自带的扫雷，在一旁的哥哥看见了，想起了自己小时候信息课在机房玩扫雷的日子，便兴致勃勃地开始教小埋扫雷。然而，小埋还是不明白 \mathrm{3bv}3bv（Bechtel's Board Benchmark Value，每局将所有非雷的方块点开所需最少左键点击数，参见扫雷网的教程 ）怎么算，于是她找到了你。
题目描述
小埋会告诉你一盘扫雷，用一个 n\times mn×m 的矩阵表示，11 是雷 ，00 不是雷，请你告诉她这盘扫雷的 \mathrm{3bv}3bv 。
周围八格没有“雷”且自身不是“雷”的方格称为“空格”，周围八格有“雷”且自身不是“雷”的方格称为“数字”，由“空格”组成的八连通块称为一个“空”。\mathrm{3bv}=\3bv= 周围八格没有“空格”的“数字”个数++“空"的个数。
如果看不懂上面的计算方式，可以看题目背景中给出的教程，或者看下面的样例解释。
注：八连通
输入格式
第一行有两个整数 nn 和 mm，代表这盘扫雷是一个 n \times mn×m 的矩阵。
后面的 nn 行每行有 mm 个整数，表示这个矩阵，每个数字为 00 或 11，11 代表是雷，00 代表不是雷。
输出格式
一个整数，代表这盘扫雷的 \mathrm{3bv}3bv 。
输入输出样例
输入 #1复制
8 8 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
输出 #1复制
13
说明/提示
1\le n,\ m\le 10001≤n, m≤1000
样例解释
# include <iostream>
# include <algorithm>
# include <cstring>
# include <math.h>
# include <stdio.h>
int num[100100];
const int N = 100100;
int step[8][2] = {{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}};
int map[1010][1010];
int mark[1010][1010];
int tot = 0;
int n,m;
using namespace std;
void put_digit(int x, int y){//通过统计所有地雷来得到旁边的数 for(int i = 0; i < 8; i++){int xx = x + step[i][0];int yy = y + step[i][1];if(xx >= 0 && xx < n && yy >= 0 && yy < m && map[xx][yy] != 9)map[xx][yy]++;}
}
void dfs(int x, int y){//通过判断其值是否为0向外拓展来统计空白 for(int i = 0; i < 8; i++){int xx = x + step[i][0];int yy = y + step[i][1];if(xx >= 0 && xx < n && yy >= 0 && yy < m && map[xx][yy] == 0 && mark[xx][yy] == 0){mark[xx][yy] = 1;dfs(xx,yy);}}
}
int find(int x, int y){//通过判断其周围八个数字是否为0来统计 for(int i = 0; i < 8; i++){int xx = x + step[i][0];int yy = y + step[i][1];if(xx >= 0 && xx < n && yy >= 0 && yy < m && map[xx][yy] == 0)return 0;} return 1;
}
int main(){cin >> n >> m;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> map[i][j];if(map[i][j] == 1)map[i][j] = 9;}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(map[i][j] == 9)put_digit(i,j);//将地雷旁边的数赋值 }}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(map[i][j] == 0 && mark[i][j] == 0){tot++;dfs(i,j);//统计空白数 }if(map[i][j] != 0 && map[i][j] != 9){//统计不是地雷的周围8个数不为0的数的个数 if(find(i,j) != 0){tot++;}}}}cout << tot << endl;
}
地雷
题目背景
小埋总是在家中打游戏，一天，她突然想玩Windows自带的扫雷，在一旁的哥哥看见了，想起了自己小时候信息课在机房玩扫雷的日子，便兴致勃勃地开始教小埋扫雷。然而，小埋还是不明白 \mathrm{3bv}3bv（Bechtel's Board Benchmark Value，每局将所有非雷的方块点开所需最少左键点击数，参见扫雷网的教程 ）怎么算，于是她找到了你。
题目描述
小埋会告诉你一盘扫雷，用一个 n\times mn×m 的矩阵表示，11 是雷 ，00 不是雷，请你告诉她这盘扫雷的 \mathrm{3bv}3bv 。
周围八格没有“雷”且自身不是“雷”的方格称为“空格”，周围八格有“雷”且自身不是“雷”的方格称为“数字”，由“空格”组成的八连通块称为一个“空”。\mathrm{3bv}=\3bv= 周围八格没有“空格”的“数字”个数++“空"的个数。
如果看不懂上面的计算方式，可以看题目背景中给出的教程，或者看下面的样例解释。
注：八连通
输入格式
第一行有两个整数 nn 和 mm，代表这盘扫雷是一个 n \times mn×m 的矩阵。
后面的 nn 行每行有 mm 个整数，表示这个矩阵，每个数字为 00 或 11，11 代表是雷，00 代表不是雷。
输出格式
一个整数，代表这盘扫雷的 \mathrm{3bv}3bv 。
输入输出样例
输入 #1复制
8 8 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
输出 #1复制
13
说明/提示
1\le n,\ m\le 10001≤n, m≤1000
样例解释
# include <iostream>
# include <algorithm>
# include <cstring>
# include <math.h>
# include <stdio.h>
int num[100100];
const int N = 100100;
int step[8][2] = {{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}};
int map[1010][1010];
int mark[1010][1010];
int tot = 0;
int n,m;
using namespace std;
void put_digit(int x, int y){//通过统计所有地雷来得到旁边的数 for(int i = 0; i < 8; i++){int xx = x + step[i][0];int yy = y + step[i][1];if(xx >= 0 && xx < n && yy >= 0 && yy < m && map[xx][yy] != 9)map[xx][yy]++;}
}
void dfs(int x, int y){//通过判断其值是否为0向外拓展来统计空白 for(int i = 0; i < 8; i++){int xx = x + step[i][0];int yy = y + step[i][1];if(xx >= 0 && xx < n && yy >= 0 && yy < m && map[xx][yy] == 0 && mark[xx][yy] == 0){mark[xx][yy] = 1;dfs(xx,yy);}}
}
int find(int x, int y){//通过判断其周围八个数字是否为0来统计 for(int i = 0; i < 8; i++){int xx = x + step[i][0];int yy = y + step[i][1];if(xx >= 0 && xx < n && yy >= 0 && yy < m && map[xx][yy] == 0)return 0;} return 1;
}
int main(){cin >> n >> m;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> map[i][j];if(map[i][j] == 1)map[i][j] = 9;}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(map[i][j] == 9)put_digit(i,j);//将地雷旁边的数赋值 }}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(map[i][j] == 0 && mark[i][j] == 0){tot++;dfs(i,j);//统计空白数 }if(map[i][j] != 0 && map[i][j] != 9){//统计不是地雷的周围8个数不为0的数的个数 if(find(i,j) != 0){tot++;}}}}cout << tot << endl;
}