题解 P4380 【[USACO18OPEN]Multiplayer Moo S】

tribool4_in · 2020-11-04 13:49:32 · 题解

前言：

此题解非正解（我是不会承认我不会正解的），只能写个暴力啦，况且暴力不开 O2 似乎也能过（只能怪数据太弱）

第一问

似乎没啥好说的，Dfs 或 Bfs 并运用 Flood-Fill 算法（话说我原来还不知道这个连通块算法有这个名字）求连通块即可 板子大法好。

上代码：

int bfs1(int x, int y) {
    int ans(0);
    queue<node> que;
    node t, s;
    t = (node){x, y};
    mark[x][y] = 1;
    que.push(t);
    while (!que.empty()) {
        t = que.front();
        que.pop();
        ans++;
        for (int i = 0; i < 4; i++) {
            s.x = t.x + dxy[i][0];
            s.y = t.y + dxy[i][1];
            if (s.x >= 1 && s.x <= n && s.y >= 1 && s.y <= n && !mark[s.x][s.y] && mp[s.x][s.y] == mp[t.x][t.y]) {
                mark[s.x][s.y] = 1;
                que.push(s);
            }
        }
    }
    return ans;
}

第二问

上暴力！

对于每两个相邻的点，判断它们能否组队，如果可以则计算组队后的最大领域即可。

但是，要是搜重复了呢？要知道这是必然发生的。咋办呢？

MAP 大法好！！！

定义 map<int, map<int, bool> > vis; ，而 vis[a][b] 表示这两点是否已经试组队过，再在暴力时判断一下即可。

上代码菜：

int bfs2(int x, int y, int x1, int y1) {
    memset(mark, 0, sizeof(mark));
    int ans(0);
    int used1 = mp[x][y], used2 = mp[x1][y1];
    queue<node> que;
    node t, s;
    t = (node){x, y};
    mark[x][y] = 1;
    que.push(t);
    while (!que.empty()) {
        t = que.front();
        que.pop();
        ans++;
        for (int i = 0; i < 4; i++) {
            s.x = t.x + dxy[i][0];
            s.y = t.y + dxy[i][1];
            if (s.x >= 1 && s.x <= n && s.y >= 1 && s.y <= n && !mark[s.x][s.y] && (mp[s.x][s.y] == used1 || mp[s.x][s.y] == used2)) {
                mark[s.x][s.y] = 1;
                que.push(s);
            }
        }
    }
    return ans;
}

主程序部分：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 0; k < 4; k++) { // 每两个相邻的点 
            int frx = i + dxy[k][0];
            int fry = j + dxy[k][1];
            if (frx >= 1 && frx <= n && fry >= 1 && fry <= n && mp[i][j] != mp[frx][fry] && !vis[mp[i][j]][mp[frx][fry]]) {
                ans2 = max(ans2, bfs2(i, j, frx, fry)), vis[mp[i][j]][mp[frx][fry]] = vis[mp[frx][fry]][mp[i][j]] = 1;
            }
        }
    }
}

最终代码:

#include <bits/stdc++.h>
const int N = 3e2 + 5;
using namespace std;
inline int read() {
    int s=0, w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int n, ans1, ans2;
int dxy[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int mp[N][N];
bool mark[N][N];
map<int, map<int, bool> > vis;
struct node {
    int x;
    int y;
};
int bfs1(int x, int y) {
    int ans(0);
    queue<node> que;
    node t, s;
    t = (node){x, y};
    mark[x][y] = 1;
    que.push(t);
    while (!que.empty()) {
        t = que.front();
        que.pop();
        ans++;
        for (int i = 0; i < 4; i++) {
            s.x = t.x + dxy[i][0];
            s.y = t.y + dxy[i][1];
            if (s.x >= 1 && s.x <= n && s.y >= 1 && s.y <= n && !mark[s.x][s.y] && mp[s.x][s.y] == mp[t.x][t.y]) {
                mark[s.x][s.y] = 1;
                que.push(s);
            }
        }
    }
    return ans;
}
int bfs2(int x, int y, int x1, int y1) {
    memset(mark, 0, sizeof(mark));
    int ans(0);
    int used1 = mp[x][y], used2 = mp[x1][y1];
    queue<node> que;
    node t, s;
    t = (node){x, y};
    mark[x][y] = 1;
    que.push(t);
    while (!que.empty()) {
        t = que.front();
        que.pop();
        ans++;
        for (int i = 0; i < 4; i++) {
            s.x = t.x + dxy[i][0];
            s.y = t.y + dxy[i][1];
            if (s.x >= 1 && s.x <= n && s.y >= 1 && s.y <= n && !mark[s.x][s.y] && (mp[s.x][s.y] == used1 || mp[s.x][s.y] == used2)) {
                mark[s.x][s.y] = 1;
                que.push(s);
            }
        }
    }
    return ans;
}
int main() {
    // freopen("multimoo.in", "r", stdin);
    // freopen("multimoo.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            mp[i][j] = read();
    for (int i = 1; i <= n; i++) // 第一问 
        for (int j = 1; j <= n; j++)
            if (!mark[i][j])
                ans1 = max(ans1, bfs1(i, j)); // 枚举每个点求连通块 
    printf("%d\n", ans1);

    memset(mark, 0, sizeof(mark));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < 4; k++) { // 每两个相邻的点 
                int frx = i + dxy[k][0];
                int fry = j + dxy[k][1];
                if (frx >= 1 && frx <= n && fry >= 1 && fry <= n && mp[i][j] != mp[frx][fry] && !vis[mp[i][j]][mp[frx][fry]]) {
                    ans2 = max(ans2, bfs2(i, j, frx, fry)), vis[mp[i][j]][mp[frx][fry]] = vis[mp[frx][fry]][mp[i][j]] = 1;
                }
            }
        }
    }
    printf("%d\n", ans2);
    return 0;
}