广搜求救T-T
  • 板块灌水区
  • 楼主RainBow_doge
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/7/18 19:53
  • 上次更新2023/11/3 09:02:52
查看原帖
广搜求救T-T
920244
RainBow_doge楼主2023/7/18 19:53

本蒟蒻用广搜做的,样例过了,为什么过不去(T-T)(题很简单,神犇求勿喷)

/*
题目描述
指挥部被突来的洪水淹没了,还好指挥部有在某些重要的地方起一些围墙,用 * 号表示,而一个封闭的 *号 区域洪水是进不去的……

现在给出指挥部的围墙建设图,问指挥部没被淹到的重要区域(由 0 表示)有多少。

输入
第一行是两个数,x 和 y(x,y≤500)。

第二行及以下是一个由 * 和 0 组成的 x*y 的图。

输出
输出没被水淹没的指挥部的 0 的数量(计算被 * 围住的 0 的个数)。

样例
输入复制
4 5
00000
00*00
0*0*0
00*00
输出复制
1
输入复制
5 5
*****
*0*0*
**0**
*0*0*
*****
输出复制
5
*/
#include<bits/stdc++.h> 
using namespace std;
//最近练广搜,看到这道题发现以前做过类似的,就搬过来了,结果样例过了,就是不对T-T 
int n,m;
char a[510][510];
int b[6100000][3];//广搜路径 
int fx[5]={0,0,1,0,-1}; //右下左上 
int fy[5]={0,1,0,-1,0}; 
int rear=1,head=1; 
int main(){ 
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        } 
    }
    int tx;
    int ty;
//绕圈式搜索,确保不落下一个,搜不到的地方一定被包了(试过好几个,很蒻的结论。。。。) 
    for(int i=1;i<=n;i++){
        if(a[i][1]=='0'){
        head=1;
    rear=1;
     b[1][1]=i;
    b[1][2]=1;
        a[i][1]='*';//把搜到的都变成围墙 
    while(head<=rear){
        for(int i=1;i<=4;i++){
            tx=b[head][1]+fx[i];
            ty=b[head][2]+fy[i];
            if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&a[tx][ty]=='0'){
                rear++;
                a[tx][ty]='*';
                b[rear][1]=tx;
                b[rear][2]=ty;

            }
        }
        head++;
    }   
        }
    }
        for(int i=1;i<=m;i++){
        if(a[1][i]=='0'){
        head=1;
    rear=1;
     b[1][1]=1;
    b[1][2]=i;
        a[1][i]='*';
    while(head<=rear){
        for(int i=1;i<=4;i++){
            tx=b[head][1]+fx[i];
            ty=b[head][2]+fy[i];
            if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&a[tx][ty]=='0'){
                rear++;
                a[tx][ty]='*';
                b[rear][1]=tx;
                b[rear][2]=ty;

            }
        }
        head++;
    }   
        }
    }
        for(int i=1;i<=m;i++){
        if(a[n][i]=='0'){
        head=1;
    rear=1;
     b[1][1]=n;
    b[1][2]=i;
        a[n][i]='*';
    while(head<=rear){
        for(int i=1;i<=4;i++){
            tx=b[head][1]+fx[i];
            ty=b[head][2]+fy[i];
            if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&a[tx][ty]=='0'){
                rear++;
                a[tx][ty]='*';
                b[rear][1]=tx;
                b[rear][2]=ty;

            }
        }
        head++;
    }   
        }
    }
        for(int i=1;i<=n;i++){
        if(a[i][m]=='0'){
        head=1;
    rear=1;
     b[1][1]=i;
    b[1][2]=m;
        a[i][m]='*';
    while(head<=rear){
        for(int i=1;i<=4;i++){
            tx=b[head][1]+fx[i];
            ty=b[head][2]+fy[i];
            if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&a[tx][ty]=='0'){
                rear++;
                a[tx][ty]='*';
                b[rear][1]=tx;
                b[rear][2]=ty;

            }
        }
        head++;
    }   
        }
    }
    //搜到的都变成围墙了,把0计数输出 
    int k=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
    if(a[i][j]=='0'){
            k++;
        }
        }

    }
    cout<<k;

    //样例过了,但就是对不了,神犇勿喷
    return 0;//好习惯 
}
2023/7/18 19:53
加载中...