- 2-7 有几个岛屿
- 2018-12-13 21:29:14 @
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cctype>
#include <stack>
#include <map>
#include <sstream>
#include <set>
#include <queue>
const int maxn=105;
using namespace std;
int A[maxn][maxn];
bool visited[maxn][maxn];
int cnt=0;
int m,n;
int fx[][2]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs(int r,int c)
{
queue<int> que;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(A[i][j]==1&&visited[i][j]==false)
{
que.push(i*n+j);
visited[i][j]=true;
while(!que.empty())
{
int num=que.front();
que.pop();
int ti=num/n;
int tj=num%n;
for(int k=0;k<4;k++)
{
int tti=ti+fx[k][0];
int ttj=tj+fx[k][1];
if(tti>=0&&tti<=m&&tti>=0&&ttj<=n&&A[tti][ttj]==1&&visited[tti][ttj]==false)
{
que.push(tti*n+ttj);
visited[tti][ttj]=true;
}
}
}
cnt++;
}
}
}
}
int main()
{
cin>>m>>n;
string s;
for(int i=0;i<m;i++)
{
cin>>s;
for(int j=0;j<s.size();j++)
{
A[i][j]=s[j]-'0';
}
}
bfs(0,0);
cout<<cnt;
return 0;
}
1 条评论
-
yejun LV 10 MOD @ 2018-12-16 19:44:27
查了下,这题样例错了,现在题面已更新。
- 1
信息
- 难度
- 6
- 分类
- (无)
- 标签
- 递交数
- 120
- 已通过
- 30
- 通过率
- 25%
- 被复制
- 7
- 上传者