8、扫雷
题目 扫雷
思路分析
本来想用前缀和 但是边边角角无法框出3*3的范围
好像也行 在外层都加上一层0
不对 也不行 二维前缀和是以某点为右下角确定的一个矩阵 只能统计到其左上角的数量
只能暴力吗 暂时没想到好的方法 先暴力把一半分拿下吧
暴力的话发现 还是在最外层加上一圈0比较方便
然后从1,1枚举到n,n 对每个点进行检查 若该点是1 就直接标记为9 若不是1 就分别从左右上下左上左下右上右下8个方向检查……嘶 还是得想办法把一个区域的总和快速算出来 这样实在太麻烦了
好像又能用前缀和…… 对某个点来说 看以它为中心的3*3的方格的总和 可以用它右下角的点的二维前缀和求出来
具体来说 把它右下角的点当做x1,y1，左上角的点当成x2,y2
那么这个3*3的窗口的总和就是 \(s[x1,y1]-s[x1,y2-1]-s[x2-1,y1]+s[x2-1,y2-1]\)
边界情况也适用
所以应该是可行的
那么就是 对于每个点i,j 看该点是是不是1 不是1 就拿i+1,j+1和i-1,j-1做二维前缀和的求值
现在就是考虑 怎么在最外层加上一圈0 左上加0可以直接从1开始读入 但是右下的话
要怎么做 其实本身就是0 读入的时候从1读到n,m 用的时候n,m放大一个用就行了
注意的是 构造前缀和的时候 要把n+1,m+1也构造进去
还以为只能拿一半 没想到这题就一个案例……直接20分到手了 啊这 这也太……
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N][N],s[N][N],ans[N][N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
n++,m++;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(a[i][j]==1)
ans[i][j]=9;
else //x2,y2 x2,y1-1 x1-1,y2 x1-1,y1-1
ans[i][j]=s[i+1][j+1]-s[i+1][j-1-1]-s[i-1-1][j+1]+s[i-1-1][j-1-1];
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
💬 评论