제출 #1361938

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

tracks

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

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

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 find_max_shortest_path(int startNode) {
  vector<int> dist(curr + 1, -1);
  queue<int> q;

  q.push(startNode);
  dist[startNode] = 1;

  while (!q.empty()) {
    int u = q.front();
    q.pop();

    max_depth = max(max_depth, dist[u]);

    for (int neighbor : adj[u]) {
      if (dist[neighbor] == -1) {
        dist[neighbor] = dist[u] + 1;
        q.push(neighbor);
      }
    }
  }
}

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 {
    find_max_shortest_path(1);
    cout << max_depth << "\n";
  }

  return 0;
}

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