bfs未过36分求助

dist_22r @ 2022-10-27 19:36:38

#include<bits/stdc++.h>
using namespace std;
int h,t,num=0,s,n,dirx[4]={-1,0,1,0},diry[4]={0,1,0,-1},b[1001][1001];
char a[1001][1001],d[1001][1001];
struct cell{
    int x,y;
}c[1001];
void bfs(int dx,int dy)
{
    h=0;
    t=1;
    c[1].x=dx;
    c[1].y=dy;
    b[dx][dy]=0;
    while(h<t)
    {
        h++;
        for(int g=0;g<4;g++)
        {
            int nx=c[h].x+dirx[g];
            int ny=c[h].y+diry[g];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&b[nx][ny]!=0)
            {
                t++;
                c[t].x=nx;
                c[t].y=ny;
                b[nx][ny]=0;
            }
        }
    }
    num++;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            if(a[i][j]!='.')
                b[i][j]=1;
            else
                b[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(b[i][j]!=0)
            {
                bfs(i,j);
            }
        }
    }
    s=num;
    num=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]=='.'||a[i+1][j]=='.'||a[i][j+1]=='.'||a[i-1][j]=='.'||a[i][j-1]=='.')
            {
                d[i][j]='.';
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]=d[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]!='.')
                b[i][j]=1;
            else
                b[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(b[i][j]!=0)
            {
                bfs(i,j);
            }
        }
    }
    cout<<s-num<<endl;
    return 0;
}

by Fri59h2 @ 2022-10-30 22:16:04

我也36，过了前三个

by Fri59h2 @ 2022-10-31 10:43:10

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void dfs(int end,char map[][end],int flag[][end],int st,int sy,int* biao){
    int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    int i;
    if(map[st][sy] == '#' && flag[st][sy] == 0){
        flag[st][sy] = 1;
        if(map[st-1][sy] == '#' &&map[st][sy-1] == '#'&&map[st+1][sy] == '#'&&map[st][sy+1] == '#')
            *biao = 1;
        for(i = 0; i <= 3; ++i){
            int tx = st + next[i][0];
            int ty = sy + next[i][1];
            if(tx < 0 || tx >= end || ty < 0 || ty >= end)
                continue;
            dfs(end,map,flag,tx,ty,biao);
        }
    }
}

int main()
{
    int count1 = 0;
    int jilu = 0;
    int n,i = 0,j,count = 0;
    scanf("%d",&n);
    char map[n][n];
    int flag[n][n];
    memset(flag,0,sizeof(flag));
    while(i < n){
        scanf("%s",map[i++]);
    } // 记录地图 
    for(i = 1; i < n; ++i){
        for(j = 1; j < n; ++j){
            if(map[i][j] == '#' && flag[i][j] == 0){
                dfs(n,map,flag,i,j,&jilu);
                ++count1;
                if(jilu == 1)
                    ++count;
                jilu = 0;
            }
        }
    }
    printf("%d",count1-count);
 } 

by Fri59h2 @ 2022-10-31 10:44:08

@ZZR0930 更正之后的丑陋代码倒是可以过的

by tiandudu__11 @ 2022-11-29 13:23:37

hack:

输入:

9
########.
########.
########.
########.
....#....
.########
.########
.########
.######## 

正确输出：

0

你的输出：

-1

by dist_22r @ 2023-03-12 11:58:50

@tiandudu_11 所以到底是哪里有问题呀

by tiandudu__11 @ 2023-03-12 12:59:12

@ZZR0930 就是你的代码会判断成“淹没前有1个小岛，淹没后有2个小岛，1-2=-1”

你可能要这么处理：

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]=='#'&&(a[i+1][j]=='.'||a[i][j+1]=='.'||a[i-1][j]=='.'||a[i][j-1]=='.')){
                a[i][j]='-';//"-"是指原本是陆地，淹没后成海洋的地方
            }
        }
    }

不能以“-”作为起点，但是在搜索过程中可以经过“-”

by Lucyna_Kushinada @ 2023-07-11 16:51:18

用dfs