1 solutions

  • 2
    @ 2022-1-6 18:08:09

    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