_L.Y.H._ 2022-11-30 21:30 采纳率: 70%
浏览 11
已结题

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

一道深度优先搜索(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

图片,做分割用

img

代码

#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(超时)请问怎么修改?

  • 写回答

1条回答 默认 最新

  • mike_code 2022-12-06 07:36
    关注

    此题如果用dfs会超时,可以改用bfs(广度优先搜索)解题

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 12月25日
  • 已采纳回答 12月20日
  • 创建了问题 11月30日

悬赏问题

  • ¥20 家用射频美容仪技术规格
  • ¥25 matlab数值溢出该怎么解决?
  • ¥15 大家帮我看看为什么错了
  • ¥15 unity互动琴弦抖动效果
  • ¥15 做了个的二极管反向饱和电流测量电路,但是测试达不到效果
  • ¥15 nginx无证书访问https失败
  • ¥15 树莓派启动AP热点传入数据
  • ¥15 multisim中关于74ls192n和DSWPK开关的问题(相关搜索:计数器)
  • ¥15 在误装Windows server2019 后如何利用Windows.old恢复?
  • ¥20 代码实现状态连接包过滤防火墙的设计与实现