L2-048 寻宝图

题目 L2-048 寻宝图

思路分析

洪水灌溉

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

//const int N=1010,M=1010;
vector<vector<char>> g;
vector<vector<bool>> st;
//char g[N][M];
//bool st[N][M];
int n,m;
int res=0,res2=0;

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){
	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && !st[x][y];
}
void dfs(int x,int y,bool& havebz){

	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
        if(isVaild(nx,ny) && g[nx][ny]!='0'){
            if(g[nx][ny]!='1') havebz=true;
            st[nx][ny]=true;
			dfs(nx,ny,havebz);
        }
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;
    g.resize(n,vector<char> (m));
    st.resize(n,vector<bool> (m,false));
	for(int i=0;i<n;i++){
        string s;cin>>s;
        for(int j=0;j<m;j++){
            g[i][j]=s[j];
        }
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(g[i][j]!='0' && !st[i][j]){
                bool havebz=false;
                if(g[i][j]!='1')
                    havebz=true;
				st[i][j]=true;
				dfs(i,j,havebz);
				res++;
                if(havebz) res2++;
			}
		}
	}
	cout<<res<<" "<<res2<<endl;

	return 0;
}

同类题型

视频讲解

⬅️ L2-047 锦标赛 🏠 00-天梯赛 ➡️ L2-049 鱼与熊掌