제출 #307305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
307305		tieunhi	Zoo (COCI19_zoo)	C++14	110 / 110	216 ms	45944 KiB

zoo

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, m, root[N*N];
char c[N][N];
vector<int> g[N*N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int inline encode(int x, int y) {
    return (x - 1) * m + y;
}
int get_root(int u) {
    return (root[u] == 0) ? u : root[u] = get_root(root[u]);
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
        }
    }

    // Merge same components
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (c[i][j] == '*') continue;
            for (int dir = 0; dir < 4; dir++) {
                int x = i + dx[dir];
                int y = j + dy[dir];
                if (x > n || x < 1 || y > m || y < 1) continue;
                if (c[x][y] != c[i][j]) continue;
                
                int p = get_root(encode(i, j));
                int q = get_root(encode(x, y));
                if (p != q) {
                    root[p] = q;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (c[i][j] == '*') continue;
            for (int dir = 0; dir < 4; dir++) {
                int x = i + dx[dir];
                int y = j + dy[dir];
                if (x > n || x < 1 || y > m || y < 1) continue;
                if (c[x][y] == c[i][j] || c[x][y] == '*') continue;
                
                int p = get_root(encode(i, j));
                int q = get_root(encode(x, y));
                g[p].push_back(q);
                g[q].push_back(p);
            }
        }
    }


    vector<int> d((n+1)*(m+1) + 1, 0);
    queue<int> q;
    int root = get_root(encode(n, m));
    q.push(root); d[root] = 1;
    int res = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        res = max(res, d[u]);
        for (auto v : g[u]) {
            if (d[v]) {
                continue;
            } else {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    cout <<res;
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65