TLE零分BFS求dalao指导

wuxikai @ 2024-09-25 17:01:10

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7;
char mp[N][N];
int vis[N][N],cnt[N*N],dx[]={0,0,-1,1},dy[]={1,-1,0,0},n;
int H;
void bfs(int x,int y){
    H++;
    queue<pair<int,int>> q;
    q.push({x,y});
    vis[x][y]=H;
    while(!q.empty()){
        int tx=q.front().first;
        int ty=q.front().second;
        vis[tx][ty]=H;
        int color;
        if(mp[tx][ty]=='1') color=1;
        else color=0;
        for(int i=0;i<4;i++){
            int dxx=x+dx[i];
            int dyy=y+dy[i];
            if(dxx<1||dxx>n||dyy<1||dyy>n||vis[x][y]==H||mp[dxx][dyy]==color){
                continue;
            }
            vis[x][y]=H;
            q.push({x,y});
        }
    }
}
int main()
{
    int q;
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        string s;
        cin >> s;
        int len=s.length();
        s="%"+s;
        for(int j=1;j<=len;j++){
            mp[i][j]=s[j];
        }
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout << mp[i][j];
        }
        cout << '\n';
    }
    */
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i][j]==0){
                bfs(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cnt[vis[i][j]]++;
        }
    }
    while(q--){
        int x,y;
        cin >> x >> y;
        cout << cnt[vis[x][y]] << '\n';
    }
}

by lichenxi108 @ 2024-09-25 17:13:33

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7;
char mp[N][N];
int vis[N][N],cnt[N*N],dx[]={0,0,-1,1},dy[]={1,-1,0,0},n;
int H;
void bfs(int x,int y){
    H++;
    queue<pair<int,int>> q;
    q.push({x,y});
    vis[x][y]=H;
    while(!q.empty()){
        int tx=q.front().first;
        int ty=q.front().second;
      q.pop(); 
        vis[tx][ty]=H;
        int color;
        if(mp[tx][ty]=='1') color=1;
        else color=0;
        for(int i=0;i<4;i++){
            int dxx=x+dx[i];
            int dyy=y+dy[i];
            if(dxx<1||dxx>n||dyy<1||dyy>n||vis[x][y]==H||mp[dxx][dyy]==color){
                continue;
            }
            vis[x][y]=H;
            q.push({x,y});
        }
    }
}
int main()
{
    int q;
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        string s;
        cin >> s;
        int len=s.length();
        s="%"+s;
        for(int j=1;j<=len;j++){
            mp[i][j]=s[j];
        }
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout << mp[i][j];
        }
        cout << '\n';
    }
    */
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i][j]==0){
                bfs(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cnt[vis[i][j]]++;
        }
    }
    while(q--){
        int x,y;
        cin >> x >> y;
        cout << cnt[vis[x][y]] << '\n';
    }
}

试试看

by lichenxi108 @ 2024-09-25 17:17:28

改了一下，在IDE上没有TLE，但没有过样例。

by lichenxi108 @ 2024-09-25 17:36:10

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7;
char mp[N][N];
int vis[N][N],cnt[N*N],dx[]={0,0,-1,1},dy[]={1,-1,0,0},n;
int H;
void bfs(int x,int y){
    H++;
    queue<pair<int,int>> q;
    q.push({x,y});
    vis[x][y]=H;
    while(!q.empty()){
        int tx=q.front().first;
        int ty=q.front().second;
        q.pop(); 
        vis[tx][ty]=H;
        for(int i=0;i<4;i++){
            int dxx=tx+dx[i];
            int dyy=ty+dy[i];
            if(dxx<1||dxx>n||dyy<1||dyy>n||vis[dxx][dyy] != 0||mp[dxx][dyy]==mp[tx][ty]){
                continue;
            }
            vis[dxx][dyy]=H;
            q.push({dxx,dyy});
        }
    }
}
int main()
{
    int q;
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> mp[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i][j]==0){
                bfs(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cnt[vis[i][j]]++;
        }
    }
    while(q--){
        int x,y;
        cin >> x >> y;
        cout << cnt[vis[x][y]] << '\n';
    }
}

试试看

by wuxikai @ 2024-09-25 20:46:20

okok现已解决问题感谢指导

by wuxikai @ 2024-09-25 20:49:32

已经对啦Thanks♪(･ω･)ﾉ