关于#深度优先#超时的问题，如何解决？(语言-c++)

Question

一道深度优先搜索（DFS）题

题目

题目背景
oibh 总部突然被水淹没了！现在需要你的救援……
题目描述
oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 + 号表示，而一个四面被围墙围住的区域洪水是进不去的。
oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 0 表示。
现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。

输入格式
第一行为两个正整数 x,yx,y。
接下来 xx 行，每行 yy 个整数，由 + 和 0 组成，表示 oibh 总部的建设图。
输出格式
输出没被水淹没的 oibh 总部的 0 的数量。

输入数据 1
4 5
00000
00+00
0+0+0
00+00
输出数据 1
1

图片，做分割用

代码

#include<bits/stdc++.h>
using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
int n,m,b[1005][1005];
bool book[1005][1005];
void dfs(int x,int y)
{
    if(x==n+1&&y==m+1)
    {    
        return;
    }
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx>=0&&ny>=0&&nx<=n+1&&ny<=m+1&&book[nx][ny]==0)
        {
            if(b[nx][ny]==0||b[nx][ny]==2)
            {
                b[x][y]=2;
                book[nx][ny]=1;
                dfs(nx,ny);
                book[nx][ny]=0;
            }
        
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        b[i][0]=b[i][m+1]=2;
    }
    for(int i=0;i<=m+1;i++)
    {
        b[0][i]=b[n+1][i]=2;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char ch;
            cin>>ch;
            if(ch=='0')
            {
                b[i][j]=0;
            }
            else b[i][j]=1;
        }
    } 
    book[0][0]=1;
    dfs(1,0);
    int s=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(b[i][j]==0)
            {
                s++;    
            }
        }
    } 
        printf("%d",s);
} 

疑问

TLE（超时）请问怎么修改？

Answer 1

此题如果用dfs会超时，可以改用bfs（广度优先搜索）解题