题解 P4961 【小埋与扫雷】

ouuan

2018-11-03 23:03:12

Solution

这题考察~~读题能力以及~~基本的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到数字将答案减一 } } ```