为什么bfs超时

 #include<queue>
#include<iostream>
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,-1,0,0};
char a[101][101];
int visit[101][101];
int s=0;
void bfs(int x,int y,int n,int m)
{
    int i,j;
    int x1,x2;
    queue<int> q;
    q.push(x*m+y);
    while(!q.empty())
    {
        int t=q.front();
        x1=t/m;x2=t%m;
        q.pop();
        visit[x1][x2]=s;
        for(i=0;i<12;i++)
        {
            
            if(x1+dx[i]>=0&&x1+dx[i]<n&&x2+dy[i]>=0&&x2+dy[i]<m&&a[x1+dx[i]][x2+dy[i]]=='#'&&visit[x1+dx[i]][x2+dy[i]]==0)
            {
            
                q.push((x1+dx[i])*m+(x2+dy[i]));
                
            }
        }
    }
}
int main()
{
    int n,m,i,j;
    cin>>n>>m;
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
    cin>>a[i][j];
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
    visit[i][j]=0;
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
    {
        if(a[i][j]=='#'&&visit[i][j]==0)
        {
            s++;
            bfs(i,j,n,m);
            //cout<<i<<" "<<j<<endl;
        }
    }
    cout<<s;
    return 0;
} 

0 条评论

目前还没有评论...

信息

ID
1051
难度
4
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
6196
已通过
2431
通过率
39%
被复制
13
上传者