大犇们救救我！60分求调！！

I_AM_Nigger @ 2024-09-17 17:22:36

#include<bits/stdc++.h>
using namespace std;
int tx[4] = {1,-1,0,0};
int ty[4] = {0,0,1,-1};
int memory[1010][1010];
int vis[1010][1010];
int mp[1010][1010];
queue <int> qx;
queue <int> qy;
int n,m;
int num = 1;
int bfs(int x,int y)
{
    int cnt = 1;
    qx.push(x);
    qy.push(y);
    vis[x][y] = 1;
    while(!qx.empty() && !qy.empty())
    {
        // cout << qx.front()+1 << " " << qy.front()+1 << '\n';
        for(int i = 0;i<4;i++)
        {
            int dx = qx.front() + tx[i];int dy = qy.front() + ty[i];
            if(dx >= 0 && dy >= 0 && dx < n && dy < n && !vis[dx][dy] && mp[qx.front()][qy.front()] != mp[dx][dy])
            {
                qx.push(dx);
                qy.push(dy);
                vis[dx][dy] = num;
                cnt++;
            }
        }
        qx.pop();qy.pop();
    }
    return cnt;
}
int main()
{
    cin >> n >> m;
    for(int i = 0;i<n;i++) 
    {
        for(int j = 0;j<n;j++)
        {
            scanf("%1d",&mp[i][j]);
        }
    }
    // for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){cout << mp[i][j] << " ";}cout << '\n';}
    while(m--)
    {
        int x,y = 0;
        cin >> x >> y;
        if(memory[x-1][y-1])
        {
            cout << memory[x-1][y-1] << '\n';
            continue;
        }
        int ans = bfs(x-1,y-1);
        for(int i = 0;i<n;i++) 
        {
            for(int j = 0;j<n;j++)
            {
                if(vis[i][j] == num)
                {
                    memory[i][j] = ans;
                }
            }
        }
        num++;
        cout << ans << '\n';
    }
    //debug
    //  for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){cout << memory[i][j] << " ";}cout << '\n';}
    return 0;
}

by jianping12_AC @ 2024-09-17 17:28:08

用深搜吧，遍历每个连通块，就可以了。

超时应该是思路不对。

wa我也不知道是什么情况。

by jianping12_AC @ 2024-09-17 17:28:34

#include <bits/stdc++.h>
using namespace std;
int n,t,cnt;
char a[1009][1009];
int flag[1009][1009];//0 未标记 1 标记一遍 2 标记两遍 
int ret[1009][1009];
int f[10][2]={{-1,0},{0,-1},{1,0},{0,1}};
void dfs1(int x,int y){
    cnt++;
    for(int i=0;i<4;i++){
        int nx=x+f[i][0];
        int ny=y+f[i][1];
        if(nx<0||nx>=n||ny<0||ny>=n) continue;
        if(a[x][y]==a[nx][ny]) continue;
        if(flag[nx][ny]==1||flag[nx][ny]==2) continue;
        flag[nx][ny]=1;
        dfs1(nx,ny);
    }
}
void dfs2(int x,int y){
    for(int i=0;i<4;i++){
        int nx=x+f[i][0];
        int ny=y+f[i][1];
        if(nx<0||nx>=n||ny<0||ny>=n) continue;
        if(a[x][y]==a[nx][ny]) continue;
        if(flag[nx][ny]==0||flag[nx][ny]==2) continue;
        flag[nx][ny]=2;
        ret[nx][ny]=cnt;
        dfs2(nx,ny);
    }   
}
int main(){
    cin>>n>>t;
     for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j]; 
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cnt=0;
            if(flag[i][j]!=0) continue;
            flag[i][j]=1;
            dfs1(i,j);
            ret[i][j]=cnt;
    //      cout<<cnt<<" cnt"<<endl;
            dfs2(i,j);
        }
    }
    while(t--){
        int l,j;
        cin>>l>>j;
        if(l>n||j>n){
            cout<<1<<endl;
        }
        else
        cout<<ret[l-1][j-1]<<endl;
    }
    return 0;
}

代码给你

by jianping12_AC @ 2024-09-17 17:30:05

话说你57到66是干什么的？

by I_AM_Nigger @ 2024-09-17 18:28:40

@jianping12_AC 是用来记忆的，这样不用重复历遍

by I_AM_Nigger @ 2024-09-17 18:29:19

@jianping12_AC 可是这个标签打的广搜啊

by I_AM_Nigger @ 2024-09-17 18:30:52

@jianping12_AC 能不能用广搜解决啊

by I_AM_Nigger @ 2024-09-17 20:42:17

快995吧！！

by jianping12_AC @ 2024-09-18 18:07:27

hem，对不起，上学了没看见，现在还需要吗？

by QZWWW @ 2024-09-18 19:01:18

@jianping12_AC 要要要！！！换了个号

by jianping12_AC @ 2024-09-18 19:22:25

80分了