제출 #1361935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361935		puntre	Tracks in the Snow (BOI13_tracks)	C++20	31.77 / 100	1612 ms	936228 KiB

tracks

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

int h, w, curr = 1;
int a[4002][4002];
bool b[4002][4002];
char ss;
vector<pair<int, int>> dif;
int label[4002][4002];
vector<set<int>> adj;

int path_size = 0;
vector<bool> visited_comp;

void fill(int start_i, int start_j) {
  queue<pair<int, int>> q;
  q.push({start_i, start_j});

  b[start_i][start_j] = 1;
  label[start_i][start_j] = curr;

  while (!q.empty()) {
    auto [i, j] = q.front();
    q.pop();

    for (auto x : dif) {
      int i_next = i + x.first, j_next = j + x.second;

      if (i_next <= h && i_next >= 1 && j_next <= w && j_next >= 1) {
        if (a[i][j] == a[i_next][j_next] && !b[i_next][j_next]) {
          b[i_next][j_next] = 1;
          label[i_next][j_next] = curr;
          q.push({i_next, j_next});
        } else if (b[i_next][j_next] && a[i][j] != a[i_next][j_next] &&
                   a[i_next][j_next] != '.') {
          adj[label[i][j]].insert(label[i_next][j_next]);
          adj[label[i_next][j_next]].insert(label[i][j]);
        }
      }
    }
  }
}
void dfs_tree(int u, int current_len) {
  visited_comp[u] = true;
  path_size = max(path_size, current_len);

  for (int neighbor : adj[u]) {
    if (!visited_comp[neighbor]) {
      dfs_tree(neighbor, current_len + 1);
    }
  }
}

int main() {

  adj.emplace_back(set<int>{0});
  dif.emplace_back(1, 0);
  dif.emplace_back(-1, 0);
  dif.emplace_back(0, 1);
  dif.emplace_back(0, -1);

  cin >> h >> w;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cin >> ss;
      a[i][j] = ss;
    }
  }

  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      if (a[i][j] == '.') {
        b[i][j] = 1;
      } else {
        if (!b[i][j]) {
          adj.emplace_back(set<int>{});
          fill(i, j);
          curr++;
        }
      }
    }
  }

  if (a[1][1] == '.') {
    cout << 0 << "\n";
    return 0;
  } else {
    visited_comp.assign(curr + 1, false);
    dfs_tree(1, 1);
    cout << path_size << "\n";
  }

  return 0;
}

• 서브태스크 1: 3.3333 / 30
• 서브태스크 2: 28.4375 / 70