P1506 拯救oibh总部

题目背景

oibh 总部突然被水淹没了！现在需要你的救援……

题目描述

oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示，而一个四面被围墙围住的区域洪水是进不去的。

oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 0 表示。

现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。

输入格式

第一行为两个正整数 x,y。

接下来 x行，每行 y个整数，由 * 和 0 组成，表示 oibh 总部的建设图。

输出格式

输出没被水淹没的 oibh 总部的 0 的数量。

输入输出样例

输入 #1复制

4 5
00000
00*00
0*0*0
00*00

输出 #1复制

1

输入 #2复制

5 5
*****
*0*0*
**0**
*0*0*
*****

输出 #2复制

5

说明/提示

对于 100\%100% 的数据，1 \le x,y \le 5001≤x,y≤500。

 

我的思路是将数组全标记为‘0’,从(1,1)开始将每个数据输入,然后从边界(0,0)开始搜,搜到‘0’就变为‘*’,这样搜的全是外围的,但后再遍历一遍,找到‘0’,有几个答案就是几,但是测试数据有一组超时了,从广搜变为了深搜

超时代码 

#include <bits/stdc++.h>
using namespace std;
char s[505][505];
  int n,m;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void bfs(){
    queue<pair<int ,int>>q;
    q.push(make_pair(0,0));
    while(!q.empty()){
        auto t=q.front();
        q.pop();
         s[t.first][t.second]='*';
        for(int i=0;i<4;i++){
                if((t.first+dx[i])>=0&&(t.first+dx[i])<=n+1&&(t.second+dy[i])>=0&&(t.second+dy[i])<=m+1&&s[t.first+dx[i]][t.second+dy[i]]=='0'){
                   q.push(make_pair(t.first+dx[i],t.second+dy[i]));
                }
        }
    }
}
int main(){
    int ans=0;
    memset(s,'0',sizeof(s));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
                cin>>s[i][j];
                if(s[i][j]==0){
                    s[i][j]='0';
                }
        }
    }
     bfs();
      for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='0'){
                ans++;
            }
        }
        }
        printf("%d",ans);
 
}

 ac代码

#include <bits/stdc++.h>
using namespace std;
char s[505][505];
  int n,m;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void dfs(int p,int q){
    if(p<0||p>n+1||q<0||q>m+1||s[p][q]=='*') return ;//
    s[p][q]='*';
    for(int i=0;i<4;i++)
    dfs(p+dx[i],q+dy[i]);
}
int main(){
    int ans=0;
    memset(s,'0',sizeof(s));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
                cin>>s[i][j];
                if(s[i][j]==0){
                    s[i][j]='0';
                }
        }
    }
     dfs(0,0);
      for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='0'){
                ans++;
            }
        }
        }
        printf("%d",ans);
 
}