제출 #1227752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227752		vyaduct	Tracks in the Snow (BOI13_tracks)	C++20	89.06 / 100	2119 ms	1114112 KiB

tracks

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

/* Somehow, we just link connected componants together
 * and find max distance to (1,1)
*/

const int mxN = 4000;
int a[mxN][mxN];
bool visited[mxN][mxN];
int color[mxN][mxN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool valid(int x, int y, int n, int m){
  return x >= 0 && x < n && y >= 0 && y < m;
}

void floodfill(int r, int c, int idx, int n, int m){
  if (!valid(r, c, n, m)) return;
  if (visited[r][c] || a[r][c] == 0) return;
  color[r][c] = idx;
  visited[r][c] = true;
  if (valid(r+1, c, n, m)){
    if (a[r+1][c] == a[r][c]) {
      floodfill(r+1, c, idx, n, m);
    }
  }
  if (valid(r-1, c, n, m)){
    if (a[r-1][c] == a[r][c]) {
      floodfill(r-1, c, idx, n, m);
    }
  }
  if (valid(r, c+1, n, m)){
    if (a[r][c+1] == a[r][c]) {
      floodfill(r, c+1, idx, n, m);
    }
  }
  if (valid(r, c-1, n, m)){
    if (a[r][c-1] == a[r][c]) {
      floodfill(r, c-1, idx, n, m);
    }
  }
}

void solve(){
  int n,m; cin>>n>>m;
  for (int i=0;i<n;i++){
    for (int j=0;j<m;j++){
      char c; cin>>c;
      visited[i][j] = false;
      color[i][j]=0;
      if (c == '.') a[i][j] = 0;
      else if (c == 'F') a[i][j] = 1;
      else a[i][j] = 2;
    }
  }

  int g=1;
  for (int i=0;i<n;i++){
    for (int j=0;j<m;j++){
      if (!visited[i][j] && a[i][j]>0){
        floodfill(i, j, g, n, m);
        g++;
      }
    }
  }
    
  vector<set<int>> adj(g);
  for (int i=0;i<n;i++){
    for (int j=0;j<m;j++){
      if (a[i][j] == 0) continue;
      for (int k=0;k<4;k++){
        int r = i+dx[k], c = j + dy[k];
        if (valid(r, c, n, m)){
          if (a[r][c]==0) continue;
          if (color[i][j] == color[r][c]) continue;
          adj[color[i][j]].insert(color[r][c]);
          adj[color[r][c]].insert(color[i][j]);
        }
      }
    }
  }

  int s = 1;
  queue<int> q;
  vector<bool> seen(g,false);
  vector<int> d(g);
  d[s] = 1;
  seen[s] = true;
  q.push(s);
  while(!q.empty()){
    int cur = q.front(); q.pop();
    for (int u: adj[cur]){
      if (!seen[u]){
        seen[u] = true;
        d[u] = d[cur]+1;
        q.push(u);
      }
    }
  }
  int mx = 0;
  for (auto dd: d) mx = max(mx, dd);
  cout << mx << endl;
}

int main(){
  solve();
  return 0;
}

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