大犇们救救我！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-18 19:24:30

#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]==0 && mp[qx.front()][qy.front()] != mp[dx][dy])
            {
                qx.push(dx);
                qy.push(dy);
                vis[dx][dy] = 1;
                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] == 1)
                {
                    memory[i][j] = ans;
                }
                vis[i][j]=0;
            }
        }
        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;
}