poj1164

bfs

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define maxn 55

struct Point
{
    int x, y;
}q[maxn * maxn];

int n, m, ans;
int map[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] =
{
{ 0, -1 },
{ -1, 0 },
{ 0, 1 },
{ 1, 0 } };

bool ok(Point &p)
{
    if (p.x < 0 || p.y < 0 || p.x >= n || p.y >= m || vis[p.x][p.y])
        return false;
    return true;
}

void bfs(int cx, int cy)
{
    int front = 0, rear = 1;
    vis[cx][cy] = true;
    q[0].x = cx;
    q[0].y = cy;
    int num = 0;
    while (front != rear)
    {
        Point p = q[front++];
        num++;
        int k = 1;
        for (int i = 0; i < 4; i++)
        {
            Point temp;
            temp.x = p.x + dir[i][0];
            temp.y = p.y + dir[i][1];
            if (!(k & map[p.x][p.y]) && ok(temp))
            {
                q[rear++] = temp;
                vis[temp.x][temp.y] = true;
            }
            k <<= 1;
        }
    }
    ans = max(ans, num);
}

int main()
{
    //freopen("t.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &map[i][j]);
    int num = 0;
    memset(vis, 0, sizeof(vis));
    ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!vis[i][j])
            {
                bfs(i, j);
                num++;
            }
    printf("%d\n%d\n", num, ans);
    return 0;
}