제출 #715527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715527		Behradm	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	1992 ms	1048576 KiB

tracks

/**
 *  In the name of GOD
 *  author : Behradm
**/
#include "bits/stdc++.h"

using namespace std;

#define sz(x) (int) ((x).size())

short dx[4] = {0, 0, 1, -1};
short dy[4] = {1, -1, 0, 0};

const int N = 4e3 + 3;
char s[N][N];
int tag[N][N];
vector<vector<pair<int, int>>> pep;
vector<int> h;
queue<int> q;

int n, m;

bool Good(int x, int y) {
  return (0 <= x && x < n && 0 <= y && y < m && s[x][y] != '.');
}

void dfs1(int i, int j, int c) {
  tag[i][j] = c;
  for (int k = 0; k < 4; k++) {
    int x = i + dx[k], y = j + dy[k];
    if (Good(x, y) && s[x][y] == s[i][j] && tag[x][y] == -1) {
      dfs1(x, y, c);
    }
  }
}

void dfs2(int i, int j, int c) {
  bool ok = 1;
  for (int k = 0; k < 4; k++) {
    int x = i + dx[k], y = j + dy[k];
    if (Good(x, y) && s[x][y] != s[i][j])
      ok = 0;
  }
  if (!ok)
    pep[c].push_back({i, j});

  tag[i][j] = c;
  for (int k = 0; k < 4; k++) {
    int x = i + dx[k], y = j + dy[k];
    if (Good(x, y) && s[x][y] == s[i][j] && tag[x][y] == -1) {
      dfs2(x, y, c);
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  if (n == 1 && m == 1)
    return cout << 1 << '\n', 0;

  memset(tag, -1, sizeof tag);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> s[i][j];
    }
  }
  
  int c = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (tag[i][j] == -1 && s[i][j] != '.')
        dfs1(i, j, c++);
    }
  }

  pep.resize(c);
  h.resize(c);
  memset(tag, -1, sizeof tag);
  c = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (tag[i][j] == -1 && s[i][j] != '.')
        dfs2(i, j, c++);
    }
  }

  q.push(0), h[0] = 1;
  int ans = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    
    for (auto [i, j] : pep[u]) {
      for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (Good(x, y) && s[x][y] != s[i][j]) {
          int v = tag[x][y];
          if (h[v] == 0) {
            q.push(v);
            h[v] = h[u] + 1;
            ans = max(ans, h[v]);
          }
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 67.8125 / 70