TLE70求调BFS

P1141 01迷宫

Konnyaku_HaveALot @ 2024-08-31 15:39:46

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,sx,sy,visited[1005][1005],a[1005][1005],cnt;
char c;
int dx[10]={ 0, 1, 0,-1, 0};
int dy[10]={ 0, 0, 1, 0,-1};
void bfs(){
    queue<pair<int,int>> q;
    q.push({sx,sy});
    visited[sx][sy]=1;
    cnt=1;
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int i=1;i<=4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(!a[x][y]){
                if(nx>0&&nx<=n&&ny>0&&ny<=n&&!visited[nx][ny]&&a[nx][ny]){
                    q.push({nx,ny});
                    visited[nx][ny]=1;
                    cnt++;
                }
            }
            if(a[x][y]){
                if(nx>0&&nx<=n&&ny>0&&ny<=n&&!visited[nx][ny]&&!a[nx][ny]){
                    q.push({nx,ny});
                    visited[nx][ny]=1;
                    cnt++;
                }
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>c;
            a[i][j]=c-'0';
        }
    }
    for(int i=1;i<=m;i++){
        cin>>sx>>sy;
        memset(visited,0,sizeof(visited));
        bfs();
        cout<<cnt<<"\n";
    }
    return 0;
}

点3,10,11+民间数据点一TLE

by Yxy7952 @ 2024-08-31 15:45:01

@Konnyaku_HaveALot

你这个是每询问一次就跑一次广搜，应该先跑完，然后询问就直接调用

by Konnyaku_HaveALot @ 2024-08-31 15:50:36

@yixingyou 感谢

by Yinsibo99 @ 2024-09-04 19:37:14


#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a,b,m,sum[55],cnttemp,temp,cntm,ave,maxtemp;

int main()
{
    cin >> n;
    if (!n)
    {
        cout << -1;
        return 0;
    }
    ave = 100.0 / n;
    for (int i = 1;i <= n;i++)
    {
        cin >> a >> b;
        sum[i] = a + b;
    }
    cin >> m;
    sort(sum + 1,sum + 1 + n);

    if (sum[1] == m)
    {
        cntm = 1;
    }
    cnttemp = 1;
    temp = sum[1];
    for (int i = 2;i <= n;i++)
    {

        if(sum[i] == sum[i-1])
        {
            cnttemp++;
        }
        else if(cnttemp>maxtemp)
        {
            temp = sum[i-1];
            maxtemp = cnttemp;
            cnttemp = 1;
        }
        else cnttemp = 1;
        if (sum[i] == m)
        {
            cntm++;
        }
    }
    if(cnttemp>maxtemp) temp=sum[n];
    cout << round(cntm * ave) << "\n" << temp;
    return 0;
}
你专栏里面的问题，AC代码放这里了

by Konnyaku_HaveALot @ 2024-09-04 19:55:50

@Yinsibo99 谢谢