BFS全re找不到原因
查看原帖
BFS全re找不到原因
638882
qiuqiuyaq楼主2023/3/6 13:04
#include <iostream>

using namespace std;

const int N = 300;

int x,y;
char a[N][N];

int ans,cnt;
bool leak;

typedef pair<int,int> PII;
PII q[ 25100];

bool st[N][N];

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

void bfs(int i,int j)
{
    int hh=0,tt=0;
    st[i][j] = true;
    
    q[0] ={i,j};
    
    while(hh <= tt)
    {
        auto t = q[hh++];
        for(int i =0;i < 4;i++ )
        {
            leak = false;
            cnt = 0;
            int u1 = t.first + dx[i];
            int u2 = t.second + dy[i];
        
            if(u1 < 1 || u1 > x || u2 < 1 || u2 > y)
            continue;
            if(a[u1][u2] == '*') continue;
            //如果当前是'#‘说明与外面的连通块有接壤
            if(a[u1][u2] == '#') leak = true;
            q[++tt] ={u1,u2};
            st[u1][u2] = true;   
            cnt++;
        }
    }
    if(!leak) ans += cnt;             
}


int main()
{
    cin >> x >> y;
    /*
    
#######
#00000#
#00*00#
#0*0*0#
#00*00#
#######
    
    
    
    */
    for(int i = 0;i <= x+2;i++ )
    {
        for(int j = 0;j <= y+2;j++ )
        {
            a[i][j] = '#';
        }
    }
    for(int i = 1;i <= x;i++ )
    {
        for(int j = 1;j <= y;j++ )
        {
            cin >> a[i][j];
        }
    }
      for(int i = 0;i <= x+1;i++ )
    {
        for(int j = 0;j <= y+1;j++ )
        {
            cout <<  a[i][j];
        }
        cout<<endl;
    }
    
    for(int i=1;i<=x;i++)
        for(int j=1;j<=y;j++)
        {
            if(a[i][j]=='0' && !st[i][j])
            {
                bfs(i,j);
            }
        }

    cout << ans;
    
}
2023/3/6 13:04
加载中...