|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include<bits/stdc++.h>
using namespace std;
char map[55][55];
int ans;
int n,m;
bool sea[55][55];
bool land[55][55];
queue<pair<int,int>>q;
int dx1[8]={-1,-1,0,1,1,1,0,-1};
int dy1[8]={0,1,1,1,0,-1,-1,-1};
int dx2[4]={-1,0,1,0};
int dy2[4]={0,1,0,-1};
void dfs(int x,int y){
for(int i=0;i<4;i++){
int xx=x+dx2[i];
int yy=y+dy2[i];
if(xx<1||yy<1||xx>n||yy>m)
continue;
if(map[xx][yy]=='0')
continue;
if(!land[xx][yy]&&map[xx][yy]=='1'){
land[xx][yy]=true;
dfs(xx,yy);
}
}
}
void bfs(int x,int y){
q.push({x,y});
while(!q.empty()){
auto t=q.front();
q.pop();
x=t.first;
y=t.second;
for(int i=0;i<8;i++){
int xx=x+dx1[i];
int yy=y+dy1[i];
if(xx<0||yy<0||xx>n+1||yy>m+1)
continue;
if(map[xx][yy]=='1'&&!land[xx][yy]){
land[xx][yy]=true;
ans++;
dfs(xx,yy);
}
if(sea[xx][yy])
continue;
if(map[xx][yy]=='1')
continue;
sea[xx][yy]=true;
q.push({xx,yy});
}
}
}
int main()
{
int t;
cin>>t;
while(t--){
ans=0;
cin>>n>>m;
memset(map,'0',sizeof(map));
memset(sea,false,sizeof(sea));
memset(land,false,sizeof(land));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>map[i][j];
}
}
sea[0][0]=true;
bfs(0,0);
}
return 0;
} |
|