sdnu oj 1136 Balloons bfs
程序员文章站
2022-05-12 12:23:00
...
注意每个答案后面要在空一行哦
经典bfs
题意是这样的(不知道图片为什么这么大…)
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <queue>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int N = 106;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
struct node
{
int x, y;
}one[N*N];
bool vis[N][N];
char a[N][N];
int der1[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int der2[8][2] = {{-1,0},{1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,1},{1,-1}};
int cnt, ans1, ans2, n;
void bfs1()
{
int i, j;
queue<node> q;
for(i = 1; i <= cnt; ++i)
{
if(!vis[one[i].x][one[i].y]) //从未遍历过的 '1' 找起, 可以作为一个连通块
{
++ans1;
q.push(one[i]);
vis[one[i].x][one[i].y] = 1;
while(!q.empty())
{
node now = q.front();
q.pop();
for(j = 0; j < 4; ++j)
{
int xx = now.x + der1[j][0];
int yy = now.y + der1[j][1];
if(xx >= 0 && xx < n && yy >= 0 && yy < n)
if(!vis[xx][yy] && a[xx][yy] == '1')
{
vis[xx][yy] = 1;
node tp;
tp.x = xx;
tp.y = yy;
q.push(tp);
}
}
}
}
}
printf("%d", ans1);
}
void bfs2()
{
int i, j;
queue<node> q;
for(i = 1; i <= cnt; ++i)
{
if(!vis[one[i].x][one[i].y])
{
++ans2;
q.push(one[i]);
vis[one[i].x][one[i].y] = 1;
while(!q.empty())
{
node now = q.front();
q.pop();
for(j = 0; j < 8; ++j)
{
int xx = now.x + der2[j][0];
int yy = now.y + der2[j][1];
if(xx >= 0 && xx < n && yy >= 0 && yy < n)
if(!vis[xx][yy] && a[xx][yy] == '1')
{
vis[xx][yy] = 1;
node tp;
tp.x = xx;
tp.y = yy;
q.push(tp);
}
}
}
}
}
printf(" %d\n\n", ans2);
}
int main()
{
int i, j;
int num = 0;
while(~scanf("%d", &n) && n)
{
getchar(); //“吃掉”换行回车
++num;
ans1 = ans2 = cnt = 0;
memset(vis, 0, sizeof vis);
memset(one, 0, sizeof one);
memset(a, '\0', sizeof a);
for(i = 0; i < n; ++i)
{
for(j = 0; j < n; ++j)
{
scanf("%c", &a[i][j]);
if(a[i][j] == '1') //记录'1'出现的位置
{
one[++cnt].x = i;
one[cnt].y = j;
}
}
getchar(); //“吃掉”换行回车
}
printf("Case %d: ", num);
bfs1();
memset(vis, 0, sizeof vis);
bfs2();
}
return 0;
}