题解：洛谷 B4557 [GESP202606 四级] 扫雷

【题目来源】洛谷B4557 [GESP202606 四级] 扫雷 - 洛谷【题目描述】小杨同学正在游玩经典游戏「扫雷」他想自己生成一个「扫雷」的地图。小杨同学希望生成的地图大小为n nn行m mm列一共n × m n \times mn×m个区块。区块行号为1 , 2 , ⋯ , n 1, 2, \cdots, n1,2,⋯,n列号为1 , 2 , ⋯ , m 1, 2, \cdots, m1,2,⋯,m。其中一些区块为雷区其它区块不为雷区。小杨同学指定了q qq个区块为雷区而其它区块均不为雷区。小杨同学希望你帮忙计算非雷区的区块每个区块与多少个雷区相邻我们定义区块相邻当且仅当两个区块至少有一个公共顶点也就是说对于不在地图边缘的区块周围8 88个区块均与其相邻。【输入】输入包含q 1 q 1q1行。第一行三个正整数n nn,m mm和q qq分别表示地图行数和列数以及雷区数量。接下来的q qq行每行有2 22个整数分别表示第i ii个雷区的行号和列号。保证输入的雷区不重复。【输出】输出n nn行每行m mm个字符使用空格分割对于第i ii行第j jj列输出地图对应区块的信息如果为雷区输出*如果不是雷区输出其相邻雷区数量输出0 00到8 88中的一个数字。【输入样例】3 4 4 1 1 1 3 2 4 3 2【输出样例】* 2 * 2 2 3 3 * 1 * 2 1【核心思想】问题分析给定n × m n \times mn×m的地图和q qq个雷区坐标需要为每个非雷区区块计算其周围8 88个方向相邻区块中雷区的数量。雷区输出*非雷区输出0 ∼ 8 0 \sim 80∼8的数字。本质是二维网格上的邻域计数问题。算法选择直接模拟八方向枚举对每个非雷区位置枚举周围8 88个方向的相邻位置统计其中雷区数量方向向量法用两个偏移数组d x [ 8 ] dx[8]dx[8]和d y [ 8 ] dy[8]dy[8]统一表示8 88个相邻方向的坐标变化关键步骤初始化创建标记数组a [ 1.. n ] [ 1.. m ] a[1..n][1..m]a[1..n][1..m]初始全为0 00标记雷区读入q qq个雷区坐标( x , y ) (x, y)(x,y)设置a [ x ] [ y ] 1 a[x][y] 1a[x][y]1邻域计数对每个非雷区位置( i , j ) (i, j)(i,j)初始化计数器cnt 0 \text{cnt} 0cnt0遍历8 88个方向k ∈ [ 0 , 7 ] k \in [0, 7]k∈[0,7]计算相邻坐标( x x , y y ) ( i d x [ k ] , j d y [ k ] ) (xx, yy) (i dx[k], j dy[k])(xx,yy)(idx[k],jdy[k])cnt ← cnt a [ x x ] [ y y ] \text{cnt} \leftarrow \text{cnt} a[xx][yy]cnt←cnta[xx][yy]记录b [ i ] [ j ] cnt b[i][j] \text{cnt}b[i][j]cnt输出结果遍历地图雷区输出*非雷区输出b [ i ] [ j ] b[i][j]b[i][j]时间/空间复杂度时间复杂度O ( n × m × 8 q ) O ( n × m ) O(n \times m \times 8 q) O(n \times m)O(n×m×8q)O(n×m)每个位置最多检查8 88个方向空间复杂度O ( n × m ) O(n \times m)O(n×m)存储雷区标记数组和计数数组八方向枚举的核心思想方向向量统一化用d x { − 1 , − 1 , − 1 , 0 , 1 , 1 , 1 , 0 } dx \{-1, -1, -1, 0, 1, 1, 1, 0\}dx{−1,−1,−1,0,1,1,1,0}和d y { − 1 , 0 , 1 , 1 , 1 , 0 , − 1 , − 1 } dy \{-1, 0, 1, 1, 1, 0, -1, -1\}dy{−1,0,1,1,1,0,−1,−1}将8 88个相邻方向的坐标变化编码为数组避免写8 88条重复的边界判断语句边界安全隐含题目未明确说明是否需要边界检查但样例和常规实现中数组开大到N 505 N 505N505且坐标从1 11开始若雷区坐标在[ 1 , n ] × [ 1 , m ] [1, n] \times [1, m][1,n]×[1,m]范围内则相邻位置可能越界如第1 11行上方。实际应增加边界判断if (xx 1 xx n yy 1 yy m)或采用更大的数组并初始化为0 00来避免越界问题空间换时间用布尔数组a aa标记雷区位置使得查询某位置是否为雷变为O ( 1 ) O(1)O(1)统计时直接累加而非逐一判断分离计算与输出先完整计算所有位置的雷数存入b bb数组再统一格式化输出避免在计算过程中混合输出逻辑适用于二维网格上的邻域统计、图像处理中的卷积基础、游戏地图生成等场景【算法标签】#普及- #模拟【代码详解】#includebits/stdc.husingnamespacestd;constintN505;// 常量地图最大尺寸intn,m,q;// n: 地图行数; m: 地图列数; q: 雷区数量intdx[8]{-1,-1,-1,0,1,1,1,0};// 8个方向的行偏移量左上、上、右上、右、右下、下、左下、左intdy[8]{-1,0,1,1,1,0,-1,-1};// 8个方向的列偏移量inta[N][N],b[N][N];// a[i][j]: 标记(i,j)是否为雷区(1是/0否); b[i][j]: (i,j)周围雷区数量intmain(){cinnmq;// 读入地图尺寸和雷区数量while(q--)// 循环读入 q 个雷区坐标{inti,j;// i: 雷区行号; j: 雷区列号cinij;a[i][j]1;// 标记该位置为雷区}for(inti1;in;i)// 遍历地图每个位置计算非雷区周围雷数for(intj1;jm;j){if(a[i][j]1)// 跳过雷区continue;intcnt0;// cnt: 当前位置周围雷区计数器for(intk0;k8;k)// 遍历8个相邻方向{intxxidx[k],yyjdy[k];// 相邻位置的坐标cnta[xx][yy];// 累加相邻位置是否为雷区}b[i][j]cnt;// 记录当前位置周围雷区数量}for(inti1;in;i)// 输出地图{for(intj1;jm;j){if(a[i][j]1)// 如果是雷区cout* ;// 输出 *else// 如果不是雷区coutb[i][j] ;// 输出周围雷区数量}coutendl;// 每行输出后换行}return0;}【运行结果】3 4 4 1 1 1 3 2 4 3 2 * 2 * 2 2 3 3 * 1 * 2 1