欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

sdnu oj 1136 Balloons bfs

程序员文章站 2022-05-12 12:23:00
...

注意每个答案后面要在空一行哦
经典bfs
题意是这样的(不知道图片为什么这么大…)
sdnu oj 1136 Balloons 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;
}


相关标签: oj