- 送给圣诞夜的极光
- 2017-07-05 16:25:26 @
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
char map[110][110];
bool visited[110][110];
int change[2][12]= {{0,-1,0,1,-2,-1,1,2,-1,0,1,0},{-2,-1,-1,-1,0,0,0,0,1,1,1,2}};
int cc=0;
int m,n;
struct point {
int r;
int c;
};
void BFS(int r,int c) {
queue<point> q;
int i,newr,newc;
bool yes;
point p;
p.r=r;
p.c=c;
q.push(p);
visited[p.r][p.c]=1;
while(!q.empty()) {
p=q.front();
q.pop();
yes=0;
for(i=0; i<12; i++) {
newr=p.r+change[0][i];
newc=p.c+change[1][i];
if(newc<=m&&newc>0&&newr<=n&&newr>0&&visited[p.r][p.c]==0) {
p.r=newr;
p.c=newc;
q.push(p);
visited[p.r][p.c]=1;
if(map[p.r][p.c]!='#')
yes=1;
}
}
if(!yes)
cc++;
}
}
int main() {
memset(map,'-',sizeof(map));
memset(visited,0,sizeof(visited));
int i,j;
cin>>n>>m;
for(i=1; i<=n; i++) {
for(j=1; j<=m; j++)
cin>>map[i][j];
}
for(i=1; i<=n; i++) {
for(j=1; j<=m; j++)
if(visited[i][j]==0&&map[i][j])
BFS(i,j);
}
cout<<cc;
return 0;
}
1 条评论
-
YLFX LV 6 @ 2017-07-05 16:50:38
哦 好了
c++
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
char map[100][100];
bool visited[100][100];
int change[2][12]= {{0,-1,0,1,-2,-1,1,2,-1,0,1,0},{-2,-1,-1,-1,0,0,0,0,1,1,1,2}};
int cc=0;
int m,n;
struct point {
int r,c;
};
queue<point> q;
void BFS(int r,int c) {
int i,newr,newc;
bool yes;
point p;
point cookie;
p.r=r;
p.c=c;
q.push(p);
visited[r][c]=1;
while(!q.empty()) {
p=q.front();
q.pop();
yes=0;
for(i=0; i<12; i++) {
newr=p.r+change[0][i];
newc=p.c+change[1][i];
if(newc<m&&newc>=0&&newr<n&&newr>=0&&visited[newr][newc]==0&&map[newr][newc]=='#') {
cookie.r=newr;
cookie.c=newc;
q.push(cookie);
visited[newr][newc]=1;
}
}
}
cc++;
}
int main() {
memset(map,'-',sizeof(map));
memset(visited,0,sizeof(visited));
int i,j;
cin>>n>>m;
for(i=0; i<n; i++) {
for(j=0; j<m; j++)
cin>>map[i][j];
}
for(i=0; i<n; i++) {
for(j=0; j<m; j++)
if(visited[i][j]==0&&map[i][j]=='#')
BFS(i,j);
}
cout<<cc;
return 0;
}
- 1