拼多多 9.1 客户端笔试题 3个题

#include <bits/stdc++.h>
using namespace std;

const int N = 210;

int n;
int w[N][N];

int main() {
    scanf("%d", &n);

    int len = n / 2;

    if (n % 2) {
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                if (i < len + 1 && j < len + 1 && j > i) w[i][j] = 2;
                else if (i < len + 1 && j > len + 1 && i + j <= n) w[i][j] = 1;
                else if (i < len + 1 && j < i ) w[i][j] = 3;
                else if (i < len + 1 && j > len + 1 && i + j > n + 1) w[i][j] = 8;
                else if (i > len + 1 && j < len + 1 && i + j <= n) w[i][j] = 4;
                else if (i > len + 1 && j > len + 1 && i < j) w[i][j] = 7;
                else if (i > len + 1 && j < len + 1 && i + j > n + 1) w[i][j] = 5;
                else if (i > len + 1 && j > len + 1 && j < i) w[i][j] = 6;
            }
        }
    } else {
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                if (i < len && j <= len && j > i) w[i][j] = 2;
                else if (i < len && j >= len && i + j <= n) w[i][j] = 1;
                else if (i <= len && j < i ) w[i][j] = 3;
                else if (i <= len && j > n - i + 1) w[i][j] = 8;
                else if (i >= len + 1 && j <= -i + n) w[i][j] = 4;
                else if (i >= len + 1 && j > i) w[i][j] = 7;
                else if (i > len + 1 && j <= len && i + j > n + 1) w[i][j] = 5;
                else if (i > len + 1 && j >= len + 1 && j < i) w[i][j] = 6;
            }
        }
    }

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            printf("%d ", w[i][j]);
        } puts("");
    }
}

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 410;

int n, m;
int g[N][N];        // g[][] 存储原图
int w[N][N], idx;    // w[][] 存储每个连通块的编号 idx
bool st[N][N];        // 表示每个点是否被遍历过
PII q[N * N];        // 数组模拟队列
int cnt[N * N];     // 记录每个连通块中点的个数

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// 将一个连通块扫描出来，全部标记为 idx
void bfs(int sx, int sy) {
    q[0] = {sx, sy};
    w[sx][sy] = idx;
    st[sx][sy] = true;
    int hh = 0, tt = 0;
    while (hh <= tt) {
        PII t = q[hh ++ ];    // 队头元素出队列
        int x = t.first, y = t.second;    // x 横坐标，y 纵坐标
        ++ cnt[idx];    // 连通块中数量加 1
        for (int d = 0; d < 4; ++ d) {    // 循环 4 个方向
            int xx = x + dx[d], yy = y + dy[d];
            if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
            if (g[xx][yy] == 0 || st[xx][yy]) continue;
            w[xx][yy] = idx;          // 点 (xx, yy) 所在连通块的编号标记为 idx
            q[ ++ tt] = {xx, yy};    // 新的点加入队列
            st[xx][yy] = true;    // 标记为这个点已经被加入过队列
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            scanf("%d", &g[i][j]);
        }
    }
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            if (!g[i][j]) continue;
            if (st[i][j]) continue;
            ++ idx;
            bfs(i, j);    // 开始扫描连通块
        }
    }

    int res = 0;    // 最终答案
    
    // i j 循环枚举每一个可以放棋子的点 (w[][] 中标记为 0 的点)
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            if (w[i][j]) continue;
            int ans = 0;    // ans 记录在这个点落一个转移的棋子能形成多大连通块
            set<int> st;    // set集合 标记这个落棋子点周围有哪些连通块的编号
            for (int d = 0; d < 4; ++ d) {
                int x = i + dx[d], y = j + dy[d];
                if (x < 0 || x >= n || y < 0 || y >= m) continue;
                if (!w[x][y]) continue;
                if (st.count(w[x][y])) continue;
                ans += cnt[w[x][y]];    // ans 加上这个连通块中的所有棋子
                st.insert(w[x][y]);
            }
            // 如果这个棋子落点能接触到的连通块数量 < 所有连通块数量
            // 则加上转移过来的这个棋子
            if (st.size() < idx) ++ans;

            res = max(res, ans);
        }
    }
    printf("%d\n", res);
}