求求大佬帮忙看一下k题代码为什么会超时[牛泪][牛泪]

#include<bits/stdc++.h>

using namespace std;

int n,m,ans=100000,s=0;

int vis[505][505],vis2[505][505];

char a[505][505];

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

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

void dfs(int x,int y){

for(int i=0;i<4;i++){

int xx=x+dx[i];

int yy=y+dy[i];

if(xx<1||x>n||yy<1||yy>m) continue;

if(a[xx][yy]=='0'&&!vis[xx][yy]){

vis[xx][yy]=1;

s++;

continue;

}

if(a[xx][yy]=='1'&&!vis2[xx][yy]){

vis2[xx][yy]=1;

dfs(xx,yy);

}

}

return ;

}

int main(){

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

cin>>a[i][j];

}

}

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

if(a[i][j]=='1'&&!vis2[i][j]){

vis2[i][j]=1;

dfs(i,j);

ans=min(ans,s);

s=0;

memset(vis,0,sizeof(vis));

}

}

}

cout<<ans;

return 0;

}

全部评论
用memset就是会超时,后面我使用了map<pair<int,int>,int> 记录0是否探查过之后就过了
点赞 回复 分享
发布于 01-23 21:38 重庆
是的,同楼上,对于数据 500 500 10101010...这样的数据就会Tle。
点赞 回复 分享
发布于 01-23 21:33 福建
乐,和第一遍我写的一模一样,memset的复杂度甚至比写两重循环大,所以相当于n^2*m^2的复杂度,我是把递归中加过'0&(30533)#39;的位置都记录下来,dfs后只把这些位置复原,就过了
点赞 回复 分享
发布于 01-23 21:30 山东

相关推荐

06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-16 18:05
何尝不是一种学历歧视呢
码农索隆:楼主明确拒绝,并说明拒绝原因了,这hr倒是挺忠心护主的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务