天梯赛练习集 L2-048 寻宝图 DFS

思路：dfs，从一块岛屿出发，搜索与之连通的所有岛屿块标记为0，计数器+1，过程中用一个变量flag标记有没有宝藏。
反思：如果用二维int数组直接存储会爆空间，所以用一维字符串数组。

#include<bits/stdc++.h>
using namespace std;
vector<string>vc;
string s;
int n,m,cot=0,flag=0,sum=0;

int d[4][2]={0,1,1,0,-1,0,0,-1};


bool ok(int x,int y)
{
	if(x>=0&&x<n&&y>=0&&y<m)
		return 1;
	return 0;
}
void dfs(int x,int y)
{
	if(vc[x][y]=='0')
		return ;
	else
	{
		if(vc[x][y]!='1')
			flag=1;
		vc[x][y]='0';
		for(int i=0;i<4;i++)
		{
			int xx=x+d[i][0];
			int yy=y+d[i][1];
			if(ok(xx,yy))
				dfs(xx,yy);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		vc.push_back(s);
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(vc[i][j]!='0')
			{
				cot++;
				dfs(i,j);
			}	
			if(flag)
			{
				sum++;
				flag=0;
			}
		}
	}		
	cout<<cot<<' '<<sum; 
 }