1 solutions
-
2
DFS做法,图从二维的(1,1)开始存,然后通过dfs从(0,0)开始遍历值为'0'的点并修改值为'*',遍历结束后再访问一遍图统计有几个'0'
#include<bits/stdc++.h> using namespace std; int n,m,ans=0; char ma[1010][1010]; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; void dfs(int x,int y){ ma[x][y]='*'; for(int i=0;i<4;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(xx>=0&&xx<=n+1&&yy>=0&&yy<=m+1&&ma[xx][yy]=='0') dfs(xx,yy); } } int main(){ memset(ma,'0',sizeof ma); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>ma[i][j]; dfs(0,0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(ma[i][j]=='0') ans++; cout<<ans<<endl; return 0; }
- 1
Information
- ID
- 1249
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 9
- Tags
- # Submissions
- 13
- Accepted
- 4
- Uploaded By