求调

shuman @ 2024-08-07 10:56:27

#include <bits/stdc++.h>
using namespace std;
char a[1010][1010];
int  vis[1010][1010];
int st[1010][1010], s[101000], n, m, p = 1, sum, u, v;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
queue<pair<int, int> > bfs;
int main()
{
    memset (vis, false, sizeof(vis));
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!st[i][j])
            {
                s[p] = 1, st[i][j] = p;
                while(!bfs.empty()) bfs.pop();
                bfs.push(make_pair(i, j));
                while (!bfs.empty())
                {
                    int xx = bfs.front().first, yy = bfs.front().second;
                    bfs.pop();
                    for (int k = 0; k < 4; k++)
                    {
                        int x = xx + dx[k], y = yy + dx[k];
                        if (x < 1 || x > n || y < 1 || y > n || a[xx][yy] - '0' + a[x][y] - '0' != 1 || vis[x][y])
                        {
                            continue;
                        }
                        st[x][y] = p, s[p]++;
                        vis[x][y] = true;
                        bfs.push(make_pair(x, y));
                    }
                }
                p += 1;
            }
    while (m--)
    {
        cin >> u >> v;
        cout << s[st[u][v]] << endl;
    }
    return 0;
}

by CATZZK @ 2024-08-07 11:13:27

#include <bits/stdc++.h>
using namespace std;
char a[1010][1010];
int  vis[1010][1010];
int st[1010][1010], s[101000], n, m, p = 1, sum, u, v;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
queue<pair<int, int> > bfs;
int main()
{
    memset (vis, false, sizeof(vis));
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!st[i][j])
            {
                st[i][j] = p;
                while(!bfs.empty()) bfs.pop();
                bfs.push(make_pair(i, j));
                vis[i][j]=true; 
                while (!bfs.empty())
                {
                    int xx = bfs.front().first, yy = bfs.front().second;
                    bfs.pop();
                    st[xx][yy] = p, s[p]++;
                    for (int k = 0; k < 4; k++)
                    {
                        int x = xx + dx[k], y = yy + dy[k];
                        if (x < 1 || x > n || y < 1 || y > n || a[xx][yy] - '0' + a[x][y] - '0' != 1 || vis[x][y])
                        {
                            continue;
                        }

                        vis[x][y] = true;
                        bfs.push(make_pair(x, y));
                    }
                }
                p += 1;
            }
    while (m--)
    {
        cin >> u >> v;
        cout << s[st[u][v]] << endl;
    }
    return 0;
}

by CATZZK @ 2024-08-07 12:12:24

#include <bits/stdc++.h>
using namespace std;
char a[1010][1010];
int  vis[1010][1010];
int st[1010][1010], s[1020105], n, m, p = 1, sum, u, v;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
queue<pair<int, int> > bfs;
int main()
{
    memset (vis, false, sizeof(vis));
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!st[i][j])
            {
                st[i][j]=p;vis[i][j]=true;
                while(!bfs.empty()) bfs.pop();
                bfs.push(make_pair(i, j));
                while (!bfs.empty())
                {
                    int xx = bfs.front().first, yy = bfs.front().second;
                    bfs.pop();
                    st[xx][yy] = p, s[p]++;
                    for (int k = 0; k < 4; k++)
                    {
                        int x = xx + dx[k], y = yy + dy[k];
                        if (x < 1 || x > n || y < 1 || y > n || a[xx][yy] - '0' + a[x][y] - '0' != 1 || vis[x][y])
                        {
                            continue;
                        }

                        vis[x][y] = true;
                        bfs.push(make_pair(x, y));
                    }
                }
                p += 1;
            }
    while (m--)
    {
        cin >> u >> v;
        cout << s[st[u][v]] << endl;
    }
    return 0;
}