题解 P4961 【小埋与扫雷】
ouuan
2018-11-03 23:03:12
这题考察~~读题能力以及~~基本的dfs
看懂题目后,按题目所述,先求出所有的数字和空格,然后对每个空格dfs求空的个数,最后对每个数字判断周围是否有空格即可。
稍微优化一点的做法是先把所有数字记录答案,dfs时遇到数字把答案减一并不继续dfs。这样码量可以略小一点(本来就不大),时间优化也不大。
### 参考代码
```
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int dir[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; //用数组记录8个方向便于枚举
void dfs(int x,int y);
int n,m,g[1010][1010],ans;
bool vis[1010][1010];
int main()
{
int i,j,k;
memset(g,-1,sizeof(g)); //初始化为-1方便判断边界
cin>>n>>m;
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
cin>>g[i][j];
}
}
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
if (g[i][j]==1)
{
for (k=0;k<8;++k)
{
if (g[i+dir[k][0]][j+dir[k][1]]==0)
{
g[i+dir[k][0]][j+dir[k][1]]=2; //把所有数字设为2
++ans;
}
}
}
}
}
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
if (g[i][j]==0&&!vis[i][j])
{
dfs(i,j);
++ans;
}
}
}
cout<<ans;
return 0;
}
void dfs(int x,int y)
{
if (vis[x][y]||g[x][y]==-1)
{
return;
}
vis[x][y]=true;
if (g[x][y]==0)
{
for (int i=0;i<8;++i)
{
dfs(x+dir[i][0],y+dir[i][1]); //dfs到空格继续dfs
}
}
else
{
--ans; //dfs到数字将答案减一
}
}
```