2848. 华师大卫星照片

char s[1005][85] = { 0 };
bool visit[1005][85] = { false };
int w, h;

void dfs(int x, int y,int& count) {
if (x > h || x<1 || y>w || y < 1)
return;
if (s[x][y] == ‘*’&&!visit[x][y]) {
visit[x][y] = true;
count++;
dfs(x + 1, y, count);
dfs(x - 1, y, count);
dfs(x, y + 1, count);
dfs(x, y - 1, count);
}
}

int main() {
cin >> w >> h;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> s[i][j];
}
}
int max = 0;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (s[i][j] == ‘*’ && !visit[i][j]) {
int count = 0;
dfs(i, j, count);
if (count > max)
max = count;
}
}
}
cout << max << endl;
return 0;
}

经典求最大联通块
百度关键词：bfs（广度优先搜索） dfs（深度优先搜索）

include

using namespace std;
struct Point
{
int xx,yy;
};
int n,m;
const int dx[4]={0,0,-1,1};
const int dy[4]={1,-1,0,0};
char tu[1010][90];
int v[1010][90];
queue Q;
int bfs(int aa,int bb)
{
while(!Q.empty()) Q.pop();
Q.push((Point){aa,bb});
v[aa][bb]=1;
int ret=1;
while(!Q.empty())
{
Point tmp=Q.front();
Q.pop();
for(int d=0;d<4;d++)
{
int fx=tmp.xx+dx[d],fy=tmp.yy+dy[d];
if(fx>=0 && fx=0 && fy>m>>n;
for(int i=0;i>tu[i];
memset(v,0,sizeof(v));
int amax=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(tu[i][j]==’*’ && !v[i][j]) amax=max(amax,bfs(i,j));
cout<<amax<<endl;
return 0;
}

经典的没有花花绕的「求最大连通块」问题。刚才我挑战了一道难题给我干晕了，来这里找找自信……（当然，那道题我还是不会）

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

char photo[1002][82];
int main() {
    uint32_t w, h; cin >> w >> h;
    for (uint32_t i = 1; i <= h; ++i)
        cin >> (photo[i] + 1);
    uint32_t max_continous = 0;
    for (uint32_t i = 1; i <= h; ++i) {
        for (uint32_t j = 1; j <= w; ++j) {
            if (photo[i][j] != '*')
                continue;
            uint32_t cnt = 1;
            photo[i][j] = '.';
            struct Pos {
                int32_t x, y;
            };
            vector<Pos> rec;
            rec.push_back({static_cast<int32_t>(i), static_cast<int32_t>(j)});
            while (!rec.empty()) {
                Pos a = rec.back();
                rec.pop_back();
                constexpr int32_t dx[4] = {1, -1, 0, 0};
                constexpr int32_t dy[4] = {0, 0, 1, -1};
                for (uint32_t i = 0; i < 4; ++i) {
                    int32_t nx = a.x + dx[i];
                    int32_t ny = a.y + dy[i];
                    if (photo[nx][ny] == '*') {
                        photo[nx][ny] = '.';
                        rec.push_back({nx, ny});
                        ++cnt;
                    }
                }
            }
            if (max_continous < cnt)
                max_continous = cnt;
        }
    }
    cout << max_continous << '\n';
}

解题报告
平民做法，纯C手工打造，无高深算法。

include

include

char bui[1005][85];
int conn=0;
typedef struct point{
int x;
int y;
}POINT;
POINT *queen[80005];

int main()
{
int w,h,i,j,count;
int head,tail;
int it,jt;
scanf(“%d %d”,&h,&w);
for(i=0;ix=i; queen[tail]->y=j; bui[i][j]=0; tail++; while(tail!=head) { it=queen[head]->x; jt=queen[head]->y;
if((jtx=it;
queen[tail]->y=jt+1;
bui[it][jt+1]=’.’;
tail++;
count++;
}
if((itx=it+1;
queen[tail]->y=jt;
bui[it+1][jt]=’.’;
tail++;
count++;
}
if((jt>0)&&(bui[it][jt-1]==’’))
{
queen[tail]=(POINT )malloc(sizeof(POINT));
queen[tail]->x=it;
queen[tail]->y=jt-1;
bui[it][jt-1]=’.’;
tail++;
count++;
}
if((it>0)&&(bui[it-1][jt]==’’))
{
queen[tail]=(POINT )malloc(sizeof(POINT));
queen[tail]->x=it-1;
queen[tail]->y=jt;
bui[it-1][jt]=’.’;
tail++;
count++;
}
head++;
}
if(count>conn)
conn=count;
}
}
printf(“%d\n”,conn);
return(0);
}

用的解法有点冗长，就是DFS。。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
char a[maxn][maxn];     //邻接矩阵 
bool vis[maxn][maxn];       //访问标记 
int Max = 0,w,h;    //Max代表最大联通集中结点个数 

int dir[4][2] = {       //方向数组 
    {-1,0},
    {0,-1},
    {0,1},
    {1,0},
};

bool inside(int r,int c) {      //越界判断 
    if(r < 0 || r >= h || c < 0 || c >= w) return false;
    return true;
}

void dfs(int r,int c,int &cnt) {
    vis[r][c] = true;       //设置访问标记 
    for(int i = 0;i < 4;i++) {      //遍历所有可能的方向（注意：不包括斜上方，斜下方） 
        int nr = r + dir[i][0];
        int nc = c + dir[i][1];
        if(inside(nr,nc) && vis[nr][nc] == false && a[nr][nc] == '*') {     //不越界，未访问，为*则是一个联通集 
            cnt++;
            dfs(nr,nc,cnt);
        }
    }
}
int main() {
    cin>>w>>h;
    for(int i = 0;i < h;i++) {
        scanf("%s",a[i]);
    }

    for(int i = 0;i < h;i++) {
        for(int j = 0;j < w;j++) {
            if(a[i][j]=='*' && vis[i][j] == false)
            {
                int cnt = 1;        //联通集定点数 
                dfs(i,j,cnt);       //遍历一个联通集 
                if(cnt > Max) Max = cnt; 
            }
        }
    }
    cout<<Max<<endl;
    return 0;
}

求最大连通区域bfs

虽然标签上说的是dfs，但是这种情况下显然bfs效率更高的，参考PAT甲级1091题

下面是代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef struct {
    int x, y;
} node;

int w, h;
bool g[1010][85];
bool visited[1010][85];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool judge(int x, int y) {
    if (x <= h && x >= 1)
        if (y <= w && y >= 1)
            if (!visited[x][y] && g[x][y])
                return true;
    return false;
}

int bfs(int x, int y) {
    node temp = node {x, y};
    queue<node> q;
    q.push(temp);
    visited[x][y] = true;
    int ans = 1;
    while(!q.empty()) {
        node v = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = v.x + dx[i], ty = v.y + dy[i];
            if (judge(tx, ty)) {
                visited[tx][ty] = true;
                q.push(node{tx, ty});
                ans++;
            }
        }
    }
    return ans;
}

int main() {
    cin >> w >> h;
    getchar();                                    /* 提前接收回车 */
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            char x;
            scanf("%c", &x);
            g[i][j] = x == '*';
        }
        getchar();                                /* 提前接收回车 */
    }
    int ans = 0;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            if (judge(i, j))
                ans = max(ans, bfs(i, j));
    printf("%d", ans);
    return 0;
}

经典求最大联通块
P.S.多年珍藏的写法[em:04]
极具收藏价值[em:06]

Same as 2054

解题报告
看错了。。。是3035
[em:13]

解题报告
各位大神，膜拜了 = =

[em:01]

看得我心塞塞的 = =

[em:15][em:08]

EOJ 3050 求次大黑区域 （两个不同的黑区域没有相邻的像素。一个黑区域的面积是其所包含的黑像素的个数。）也类似，但是求的是第二大的连通区域

include

const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};

int W,H,ans[10000],cnt=0;
char str[1005][1005];

void dfs(int a, int b){

if(str[a][b]!='*')return ;

str[a][b]='.';
ans[cnt]++;
for(int i=0; i<4; i++)
{
    int nx=a+dx[i];
    int ny=b+dy[i];
    if(nx<1||nx>H||ny<1||ny>W)continue ;
    dfs(nx,ny);
}

}
int main(){
scanf(“%d%d”,&W,&H);
getchar();
for(int i=1; i<=H; i++)
{
for(int j=1; j<=W; j++)
scanf(“%c”,&str[i][j]);
getchar();
}
for(int i=1; i<=H; i++)
for(int j=1; j<=W; j++)
if(str[i][j]==’*’){
dfs(i,j);
cnt++;
}
int max=ans[0];
for(int i=1; i<cnt; i++)
if(max<ans[i])max=ans[i];

printf("%d\n",max);

return 0;

}