P2： 卡牌遊戲

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int MAX_N = 40;
int a[MAX_N][MAX_N];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    bool done = false;
    while(!done) {
        done = true;
        for(int i = 0; i < n; i++) {
            int lt = -1;
            for(int j = 0; j < m; j++) {
                if(a[i][j] != -1) {
                    if(lt != -1 && a[i][j] == a[i][lt]) {
                        ans += a[i][j];
                        a[i][lt] = a[i][j] = -1;
                        lt = -1;
                        done = false;
                    } else {
                        lt = j;
                    }
                }
            }
        }
        for(int j = 0; j < m; j++) {
            int lt = -1;
            for(int i = 0; i < n; i++) {
                if(a[i][j] != -1) {
                    if(lt != -1 && a[i][j] == a[lt][j]) {
                        ans += a[i][j];
                        a[lt][j] = a[i][j] = -1;
                        lt = -1;
                        done = false;
                    } else {
                        lt = i;
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

P3： 搬家

DFS 的寫法：

#include<iostream>
#include<bitset>
#include<vector>
#include<map>
using namespace std;
const int SIZE = 1000;
char s[SIZE][SIZE + 1];
bitset<SIZE> visited[SIZE];
int n, m;
void read_input() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> s[i];
}
bool valid(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int cnt = 0;
// 0: 上, 1: 右, 2: 下, 3: 左
map<char, vector<int>> mask{
    {'X', {1,1,1,1}},
    {'I', {1,0,1,0}},
    {'H', {0,1,0,1}},
    {'L', {1,1,0,0}},
    {'7', {0,0,1,1}},
    {'F', {0,1,1,0}},
    {'J', {1,0,0,1}},
    {'0', {0,0,0,0}},
};
void dfs(int x, int y) {
    visited[x][y] = 1;
    cnt++;
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!valid(nx, ny) || visited[nx][ny]) {
            continue;
        }
        if(mask[s[x][y]][i] && mask[s[nx][ny]][i ^ 2]) {
            dfs(nx, ny);
        }
    }
}
void solve() {
    int an = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(s[i][j] == '0' || visited[i][j]) continue;
            cnt = 0;
            dfs(i, j);
            an = max(an, cnt);
        }
    }
    cout << an << '\n';
}
int main() {
    read_input();
    solve();
}

DSU 的寫法：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
const int MAX_N = 500;
// 0: 上, 1: 右, 2: 下, 3: 左
map<char, vector<int>> mask{
    {'X', {1,1,1,1}},
    {'I', {1,0,1,0}},
    {'H', {0,1,0,1}},
    {'L', {1,1,0,0}},
    {'7', {0,0,1,1}},
    {'F', {0,1,1,0}},
    {'J', {1,0,0,1}},
    {'0', {0,0,0,0}},
};
int n, m;
int get_grid_id(int x, int y) {
    return x * m + y;
}
int to[MAX_N * MAX_N], num[MAX_N * MAX_N];
void dsu_union(int x, int y) {
    while(x != to[x]) {
        x = to[x];
    }
    while(y != to[y]) {
        y = to[y];
    }
    if(x == y) {
        return;
    }
    if(num[x] > num[y]) {
        swap(x, y);
    }
    num[y] += num[x];
    to[x] = y;
}
int main() {
    cin >> n >> m;
    string s[MAX_N];
    for(int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for(int i = 0; i < n * m; i++) {
        to[i] = i;
        num[i] = 1;
    }
    bool have_not_zero = false;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(s[i][j] != '0') {
                have_not_zero = true;
            }
            // 上配下
            if(i + 1 < n && mask[s[i][j]][2] && mask[s[i + 1][j]][0]) {
                dsu_union(get_grid_id(i, j), get_grid_id(i + 1, j));
            }
            // 左配右
            if(j + 1 < m && mask[s[i][j]][1] && mask[s[i][j + 1]][3]) {
                dsu_union(get_grid_id(i, j), get_grid_id(i, j + 1));
            }
        }
    }
    if(have_not_zero) {
        cout << *max_element(num, num + MAX_N * MAX_N) << '\n';
    } else {
        cout << "0\n";
    }
}