为什么bfs超时 但dfsAC

#include<bits/stdc++.h>
using namespace std;
int dx[12]= {-2,-1,-1,-1,0,0,0,0,1,1,1,2};
int dy[12]= {0,-1,0,1,-2,-1,1,2,-1,0,1,0};
int n,m,ans,h[2000005][2];
bool b[105][105];
char a[105][105];
void bfs(int x,int y)
{
memset(h,0,sizeof(h));
int xx,yy,t=0,w=1;
h[w][0]=x,h[w][1]=y;
do
{
t++;
for(int i=0; i<12; i++)
{
xx=h[t][0]+dx[i],yy=h[t][1]+dy[i];
if(a[xx][yy]=='#'&&!b[xx][yy])
{
b[xx][yy]=1;
w++;
h[w][0]=xx,h[w][1]=yy;
}
}

}
while(t<w);

}
int main()
{
cin>>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]=='#'&&!b[i][j])
{
ans++;
bfs(i,j);
}
}

}
cout<<ans<<endl;
return 0;
}
————————————————bfs
#include<bits/stdc++.h>
using namespace std;
int dx[12]= {-2,-1,-1,-1,0,0,0,0,1,1,1,2};
int dy[12]= {0,-1,0,1,-2,-1,1,2,-1,0,1,0};
int n,m,ans,h[2000005][2];
bool b[105][105];
char a[105][105];
void dfs(int x,int y)
{
if(a[x][y]=='#')
{
b[x][y]=1;
for(int i=0; i<12; i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(a[xx][yy]=='#'&&!b[xx][yy])
dfs(xx,yy);
}
}

}
int main()
{
cin>>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]=='#'&&!b[i][j])
{
ans++;
dfs(i,j);
}
}

}
cout<<ans<<endl;
return 0;
}
————————————dfs

0 条评论

目前还没有评论...

信息

ID
1051
难度
4
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
5898
已通过
2283
通过率
39%
上传者