解题报告:这种水题。我竟然想不到了,,直接dfs有炸弹的点,++cnt,然后一系列循环爆炸就行了。然后想想是最优解,其实无论怎么引爆答案都是固定的,这个和先后次序无关的。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const int N=1010;
char a[N][N];
bool row[N];
bool col[N];
int n,m;
void dfs(int x,int y)
{
a[x][y]='0';
if(!row[x])
{
row[x]=true;
for(int i=0;i<m;i++)
if(a[x][i]=='1') dfs(x,i);
}
if(!col[y])
{
col[y]=true;
for(int i=0;i<n;i++)
if(a[i][y]=='1') dfs(i,y);
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
scanf("%s",a[i]);
int cnt=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]=='1')
dfs(i,j),cnt++;
cout<<cnt<<endl;
return 0;
}